#include <fstream>
#include <queue>
using namespace std;
const int Inf=9999999;
int n,m,sol,a[61][61],dint[61],dext[61];
int source,sink,r[65][65],c[65][65],v[65];
ifstream f("traseu.in");
ofstream g("traseu.out");
void read(){
     int i,j,k;
     f>>n>>m;
     while (m--){
           f>>i>>j>>k;
           a[i][j]=k;
           ++dext[i];++dint[j];
           sol+=k;}
     }
void roy_floyd(){
     int i,j,k;
     for (k=1;k<=n;++k)
      for (i=1;i<=n;++i)
       for (j=1;j<=n;++j)
        if (i!=j && a[i][k]>0 && a[k][j]>0)
         if (a[i][j]>a[i][k]+a[k][j] || a[i][j]==0)
           a[i][j]=a[i][k]+a[k][j];
     }
void build(){
     int i,j,ns,nd;
     for (i=1,ns=0;i<=n;++i)
      if  (dint[i]>dext[i]) v[++ns]=i;
     for (i=1,nd=ns;i<=n;++i)
      if (dint[i]<dext[i]) v[++nd]=i;
     source=0;sink=nd+1;
     for (i=1;i<=ns;++i){
      r[source][i]=dint[v[i]]-dext[v[i]];
      c[source][i]=0;}
     for (i=ns+1;i<=nd;++i){
      r[i][sink]=dext[v[i]]-dint[v[i]];
      c[i][sink]=0;}
     for (i=1;i<=ns;++i)
      for (j=ns+1;j<=nd;++j){
       r[i][j]=Inf;
       c[i][j]=a[v[i]][v[j]];
       c[j][i]=-c[i][j];}
     }
queue<int> q;
int d[65],t[65];  
bool u[65],cont=true;
int drum(){
    int i,k,w=Inf;
    memset(t,0,sizeof(t));
    memset(d,Inf,sizeof(d));
    d[source]=0;
    memset(u,false,sizeof(u));
    q.push(source);u[source]=true;
    while (!q.empty()){
          k=q.front();
          q.pop();u[k]=false;
          for (i=source;i<=sink;++i)
            if (r[k][i]>0)
             if (d[i]>d[k]+c[k][i]){
              d[i]=d[k]+c[k][i];
              t[i]=k;
              if (!u[i]) u[i]=true,q.push(i);
              }
          }
    cont=(t[sink]!=0);
    for (i=sink;i;i=t[i])
      if (r[t[i]][i]<w) w=r[t[i]][i];
    for (i=sink;i;i=t[i]){
        r[t[i]][i]-=w;
        r[i][t[i]]+=w;}
    return w*d[sink];
    } 
void flux(){
     do
      sol+=drum();
     while (cont);
     g<<sol;
     }
int main(){
    read();
    roy_floyd();
    build();
    flux();
    return 0;
}