# include <iostream>
# include <fstream>
# include <vector>
using namespace std ;

typedef vector < int > v1int ;
typedef vector < vector < int > > v2int ;

static
void
mfmc ( v2int & adj, v2int & cap, v2int & cst, v2int & flow ) ;

static
void
sq0 ( v2int & a , int n ) {
  v2int tmp (n); int i ;
  for ( i=0; n>i; ++i ) { v1int aux(n,0); tmp[i].swap(aux); }
  a.swap(tmp);
}

int
main ( ) {
  ifstream sin ("traseu.in"); cin.rdbuf(sin.rdbuf());
  ofstream sout ("traseu.out"); cout.rdbuf(sout.rdbuf());
  int n,m,i,k,u,v,hd,tl,ct,minct=0 ;
  cin >> n >> m ;
  int infcap=2*(n*n*n*n);
  v1int indeg (n+2,0), outdeg (n+2,0);
  v2int adj,cst,cap,flow;
  sq0(adj,n+2); sq0(cst,n+2); sq0(cap,n+2); sq0 (flow,n+2);
  for ( i=0; m>i; ++i ) {
    cin >> hd >> tl >> ct ;
    adj[hd].push_back(tl); adj[tl].push_back(hd);
    cst[hd][tl]=ct; cst[tl][hd]=-ct; cap[hd][tl]=infcap;
    minct+=ct; ++indeg[tl]; ++outdeg[hd];
  }
  for ( i=1;n>=i; ++i ) {
    if (indeg[i]>outdeg[i]) {
      adj[0].push_back(i);
      cap[0][i]=indeg[i]-outdeg[i];
    } else {
      if (indeg[i]<outdeg[i]) {
        adj[i].push_back(n+1);
        cap[i][n+1]=outdeg[i]-indeg[i];
      }
    }
  }
  v2int cst2(cst);
  mfmc(adj, cap, cst2, flow);
  for( u=1; n>=u; ++u ) { k=adj[u].size();
    for (i=0; k>i; ++i) { v=adj[u][i];
      if (0<cst[u][v]) {
        minct+=flow[u][v]*cst[u][v];
      }
    }
  }
  cout << minct << endl ;
  return 0 ;
}

static  int maxcst ( v2int & adj, v2int & cap, v2int & cst, v2int & flow ) ;
static void decrease ( v1int & val, v1int & heap, v1int & invHeap, int pos) ;
static void extract  ( v1int & val, v1int & heap, v1int & invHeap, int len) ;

static
void
mfmc ( v2int & adj, v2int & cap, v2int & cst, v2int & flow ) { // O(N M log N)
  int n = adj.size() ;
  while (true) { // N times 
    v1int dist(n), heap(n), invHeap(n), from(n) ;
    int inf=(n-1)*maxcst(adj, cap, cst, flow); // O(M)
    int count, i, k, u, v, maj , fmin;
    // Dijkstra in residual network O(M log N)
    for ( i=0; n>i; ++i ) {
      dist[i]=inf; heap[i]=i; invHeap[i]=i; from[i]=-1;
    }
    dist[0]=0;
    for ( count=n; 0<count; --count ) {
      u=heap[0]; k=adj[u].size();
      extract (dist, heap, invHeap, count-1);
      for (i=0; k>i; ++i) {
        v=adj[u][i];
        if (cap[u][v]>flow[u][v]) {
          maj=dist[u]+cst[u][v];
          if (maj<dist[v]) {
            dist[v]=maj; from[v]=u;
            decrease(dist,heap,invHeap, invHeap[v]);
          }
        }
      }
    }
    // Check if augumenting path was found.
    if (inf == dist[n-1]) {
      break ;
    }
    // Augument the flow O(N)
    fmin=-1;
    for( i=n-1; 0!=i; i=k ) { k=from[i];
      maj=cap[k][i]-flow[k][i];
      if ( (-1==fmin) || (fmin>maj) ) { fmin=maj; }
    }
    for (i=n-1; i!=0; i=k ) { k=from[i];
      flow[k][i]+=fmin; flow[i][k]-=fmin;
    }
    // Transform costs O(M)
    for ( u=0; n>u; ++u ) { k=adj[u].size();
      for ( i=0; k>i; ++i ) { v=adj[u][i];
        if ( inf != dist[u] ) {
          cst[u][v] += dist[u]-dist[v];
        }
      }
    }
  }
}

static int maxcst ( v2int & adj, v2int & cap, v2int & cst, v2int & flow ) {
  int n = adj.size(), u, i, k, v , boinit=0, nuval ;
  for ( u=0; n>u; ++u ) { k=adj[u].size();
    for ( i=0; k>i; ++i ) { v=adj[u][i];
      if (cap[u][v]>flow[u][v]) {
        if (boinit) {
          if (nuval<cst[u][v]) {
            nuval=cst[u][v];
          }
        } else {
          nuval=cst[u][v];
          boinit=1;
        }
      }
    }
  }
  return nuval;
}

static void decrease ( v1int & val, v1int & heap, v1int & invHeap, int pos) {
  int ind , tmp ;
  while ( pos != 0 ) {
    ind = (pos-1)/2;
    if (val[heap[ind]]<=val[heap[pos]]) {
      break;
    }
    tmp=heap[ind]; heap[ind]=heap[pos]; heap[pos]=tmp;
    invHeap[heap[ind]]=ind; invHeap[heap[pos]]=pos;
    pos=ind;
  }
}
static void extract  ( v1int & val, v1int & heap, v1int & invHeap, int len) {
  heap[0]=heap[len]; invHeap[heap[0]]=0; int pos=0, ind, tmp ;
  while (true) {
    ind=-1+((pos+1)*2);
    if (len<=ind) {
      break;
    }
    if (len>ind+1) {
      if (val[heap[ind]]>val[heap[1+ind]]) {
        ++ ind;
      }
    }
    if (val[heap[pos]]<=val[heap[ind]]) {
      break;
    }
    tmp=heap[ind]; heap[ind]=heap[pos]; heap[pos]=tmp;
    invHeap[heap[ind]]=ind; invHeap[heap[pos]]=pos;
  
    pos=ind;
  }
}