#include <bits/stdc++.h>

using namespace std;

const int MAXN = 60;
const int INF = 0x3f3f3f3f;

int deg[MAXN + 1];
vector < int > g[MAXN + 2];
int cap[MAXN + 2][MAXN + 2], daddy[MAXN + 2], flow[MAXN + 2][MAXN + 2], inq[MAXN + 2], d[MAXN + 2], cost[MAXN + 2][MAXN + 2], dist[MAXN + 2][MAXN + 2];
queue < int > q;

inline void add_edg(int x, int y, int z, int c) {
  g[x].push_back(y);
  g[y].push_back(x);
  cost[x][y] = c;
  cap[x][y] = z;
  cap[y][x] = -z;
}

inline int bellman(int sr, int sk) {
  memset(d, INF, sizeof d);
  inq[sr] = 1;
  q.push(sr);
  d[sr] = 0;
  while (q.empty() == false) {
    int node = q.front();
    q.pop();
    inq[node] = 0;
    for (auto it : g[node]) {
      if (flow[node][it] < cap[node][it] && d[it] > d[node] + cost[node][it]) {
        d[it] = d[node] + cost[node][it];
        daddy[it] = node;
        if (inq[it] == 0) {
          inq[it] = 1;
          q.push(it);
        }
      }
    }
  }
  return (d[sk] < INF);
}

int main()
{
    int n, m, ans = 0;
    ifstream fin("traseu.in");
    fin >> n >> m;
    memset(dist, INF, sizeof dist);
    for (int i = 0; i < m; ++i) {
      int x, y, c;
      fin >> x >> y >> c;
      dist[x][y] = c;
      --deg[x]; ++deg[y];
      ans += c;
    }
    fin.close();
    for (int i = 1; i <= n; ++i) {
      dist[i][i] = 0;
    }
    for (int k = 1; k <= n; ++k) {
      for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
          if ((i ^ j) && dist[i][j] > dist[i][k] + dist[k][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
          }
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      if (deg[i] > 0) {
        add_edg(0, i, deg[i], 0);
      } else if (deg[i] < 0) {
        add_edg(i, n + 1, -deg[i], 0);
      }
    }
    for (int i = 1; i <= n; ++i) {
      if (deg[i] > 0) {
        for (int j = 1; j <= n; ++j) {
          if (deg[j] < 0) {
            add_edg(i, j, INF, dist[i][j]);
          }
        }
      }
    }
    while (bellman(0, n + 1)) {
      int fl = INF;
      for (int node = n + 1; node != 0; node = daddy[node]) {
        fl = min(fl, cap[daddy[node]][node] - flow[daddy[node]][node]);
      }
      for (int node = n + 1; node != 0; node = daddy[node]) {
        flow[daddy[node]][node] += fl;
        flow[node][daddy[node]] -= fl;
      }
      ans += d[n + 1];
    }
    ofstream fout("traseu.out");
    fout << ans << '\n';
    fout.close();
    return 0;
}