#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <fstream>
#include <queue>

using namespace std;

ifstream in("traseu.in");
ofstream out("traseu.out");

const int INF = INT_MAX - 100000;
const int NMAX = 1 + 1 + 60;

int n, m, res;
int flow[NMAX][NMAX];
int a[NMAX];
int dist[NMAX][NMAX];
int val[NMAX];
int cost[NMAX][NMAX];
int dmin[NMAX];
bool vis[NMAX];

queue < int > q;

bool mincostflow(){

  fill(dmin, dmin + n + 2, INF);
  fill(vis, vis + n +2, 0);
  fill(a, a + n + 2, INF);

  q.push(0);
  dmin[0] = 0;
  vis[0] = true;

  while (!q.empty()){
    int node = q.front();
    vis[node] = false;

    for (int i = 0; i <= n + 1; ++i)
      if (flow[node][i] < cost[node][i] && dmin[node] + dist[node][i] < dmin[i]){
        dmin[i] = dmin[node] + dist[node][i];
        a[i] = node;
        if (!vis[i]){
          q.push(i);
          vis[i] = true;
        }
      }
    q.pop();
  }

  if (dmin[n + 1] == INF)
    return false;

  res += dmin[n + 1];
  for (int node = n + 1; node != 0; node = a[node]){
    ++flow[a[node]][node];
    --flow[node][a[node]];
  }

  return true;
}

int main()
{
  in >> n >> m;

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      dist[i][j] = INF;
  for (int i = 1; i <= n; ++i)
    dist[i][i] = 0;

  for (int i = 1; i <= m; ++i){
    int x, y, z;
    in >> x >> y >> z;
    ++val[x];
    --val[y];
    dist[x][y] = z;
    dist[y][x] = -z;
    res += z;
  }

  for (int i = 1; i <= n; ++i){
    if (val[i] < 0)
      cost[0][i] = -val[i];
    if (val[i] > 0)
      cost[i][n + 1] = val[i];
  }

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        if (dist[i][j] > 0)
          cost[i][j] = INF;

  while (mincostflow());

  out << res << '\n';

  in.close();
  out.close();
}