#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

struct MinCostMaxFlow {
  int source, sink;
  vector<bool> in_q;
  vector<int> q, dist, parent;
  vector<vector<int>> adj, cap, cost;
  MinCostMaxFlow(int n) : 
    source(n), sink(n + 1), in_q(n + 2), dist(n + 2), parent(n + 2), 
      adj(n + 2), cap(n + 2, vector<int>(n + 2)), cost(n + 2, vector<int>(n + 2)) {}
  void AddEdge(int u, int v, int c, int cst) {
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
    cap[u][v] = c;
    cost[u][v] = cst;
    cost[v][u] = -cst;
  }
  int GetMinCost() {
    int flow_cost = 0;
    while (CanIncreaseFlow()) {
      flow_cost += Augment();
    }
    return flow_cost;
  }
  bool CanIncreaseFlow() {
    fill(dist.begin(), dist.end(), (int)1e9 + 5);
    fill(in_q.begin(), in_q.end(), false);
    fill(parent.begin(), parent.end(), -1);
    q = {source};
    dist[source] = 0;
    for (int i = 0; i < (int)q.size(); ++i) {
      int node = q[i];
      in_q[node] = false;
      for (int &x : adj[node]) {
        if (cap[node][x] > 0 && dist[x] > dist[node] + cost[node][x]) {
          dist[x] = dist[node] + cost[node][x];
          parent[x] = node;
          if (!in_q[x])
            in_q[x] = true, q.emplace_back(x);
        }
      }
    }
    return parent[sink] != -1;
  }
  int Augment() {
    int node = sink, flow = (int)1e9 + 5;
    while (node != source) {
      flow = min(flow, cap[parent[node]][node]);
      node = parent[node];
    }
    node = sink;
    while (node != source) {
      cap[parent[node]][node] -= flow;
      cap[node][parent[node]] += flow;
      node = parent[node];
    }
    return flow * dist[sink];
  }
};

int main() {
  ifstream cin("traseu.in");
  ofstream cout("traseu.out");

  int n, m; cin >> n >> m;
  vector<vector<int>> adj(n), cost(n, vector<int>(n, (int)1e9 + 5));
  vector<int> deg(n);
  int sum_edges = 0;
  for (int i = 0; i < m; ++i) {
    int u, v, c; cin >> u >> v >> c; --u, --v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
    cost[u][v] = c;
    sum_edges += c;
    ++deg[u];
    --deg[v];
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (cost[i][j] > cost[i][k] + cost[k][j])
          cost[i][j] = cost[i][k] + cost[k][j];
  }
  vector<int> left, right;
  for (int i = 0; i < n; ++i) {
    if (deg[i] < 0) left.emplace_back(i);
    else if (deg[i] > 0) right.emplace_back(i);
  }
  MinCostMaxFlow g(n);
  int src = n, snk = n + 1;
  for (int &l : left)
    g.AddEdge(src, l, -deg[l], 0);
  for (int &r : right)
    g.AddEdge(r, snk, +deg[r], 0);
  
  for (int &l : left) {
    for (int &r : right)
      if (cost[l][r] != (int)1e9 + 5)
        g.AddEdge(l, r, (int)1e9 + 5, cost[l][r]);
  }
  cout << g.GetMinCost() + sum_edges << endl;
}