#include <stdio.h>
#define MAXN 60
#define MAXM 1770
#define TOTM (2 * (MAXM + 2 * MAXN))
#define INF 0x7f7f7f7f
int ut[MAXN + 2], nd[TOTM], nxt[TOTM], cpc[TOTM], fol[TOTM], cost[TOTM], dr;
int gradin[MAXN], gradout[MAXN];
int dist[MAXN + 2], prev[MAXN + 2], mch[MAXN + 2];
int q[(MAXN + 2) * (MAXN + 2)], sq, dq;
char inq[MAXN + 2];

inline int add(int x, int y, int c, int cp){
  nd[dr] = y;
  nxt[dr] = ut[x];
  ut[x] = dr;
  cost[dr] = c;
  cpc[dr] = cp;
  dr++;
}

inline void bellman(int x){
  memset(dist, 0x7f, sizeof dist);
  memset(inq, 0, sizeof inq);
  q[0] = x;
  sq = 0;
  dq = 1;
  inq[x] = 1;
  dist[x] = 0;
  int nod, poz;
  while(sq < dq){
    nod = q[sq];
    inq[nod] = 0;
    sq++;
    poz = ut[nod];
    while(poz != -1){
      if(fol[poz] < cpc[poz] && dist[nd[poz]] > dist[nod] + cost[poz]){
        dist[nd[poz]] = dist[nod] + cost[poz];
        prev[nd[poz]] = nod;
        mch[nd[poz]] = poz;
        if(!inq[nd[poz]]){
          q[dq] = nd[poz];
          dq++;
          inq[nd[poz]] = 1;
        }
      }
      poz = nxt[poz];
    }
  }
}

int main(){
  FILE *in = fopen("traseu.in", "r");
  int n, m, x, y, z, i, sum = 0, s, d;
  fscanf(in, "%d%d", &n, &m);
  s = n;
  d = n + 1;
  memset(ut, -1, sizeof ut);
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &x, &y, &z);
    x--;  y--;
    add(x, y, z, INF);
    add(y, x, -z, 0);
    gradin[y]++;
    gradout[x]++;
    sum += z;
  }
  fclose(in);
  for(i = 0; i < n; i++){
    if(gradin[i] > gradout[i]){
      add(s, i, 0, gradin[i] - gradout[i]);
      add(i, s, 0, 0);
    }
    else  if(gradout[i] > gradin[i]){
      add(i, d, 0, gradout[i] - gradin[i]);
      add(d, i, 0, 0);
    }
  }
  char augm = 1;
  int nod;
  while(augm == 1){
    bellman(s);
    if(dist[d] == INF)
      augm = 0;
    else{
      nod = d;
      while(nod != s){
        fol[mch[nod]]++;
        if(mch[nod] & 1)
          fol[mch[nod] - 1]--;
        else
          fol[mch[nod] + 1]--;
        sum += cost[mch[nod]];
        nod = prev[nod];
      }
    }
  }
  FILE *out = fopen("traseu.out", "w");
  fprintf(out, "%d", sum);
  fclose(out);
  return 0;
}