using namespace std;
#include<fstream>
#include<stdio.h>
#define inf 1000000000
 
int dist[64][64];
int gi[64],go[64];
 
int cap[64][64],cost[64][64];
int m1[64],m2[64],nm1,nm2;
 
int flux[64],cst[64],ant[64];
 
int main()
{
FILE *fin=fopen("traseu.in","r"),
     *fout=fopen("traseu.out","w");
      
int N,M,i,j,x,y,z,k;
fscanf(fin,"%d%d",&N,&M);
 
for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)
    dist[i][j]=inf;
     
int sol=0;
for(i=1;i<=M;i++)
  {
  fscanf(fin,"%d%d%d",&x,&y,&z);
  dist[x][y]=z; 
  gi[y]++;
  go[x]++;
  sol+=z;
  }
   
//Roy - Floyd
for(k=1;k<=N;k++)
 for(i=1;i<=N;i++)
   for(j=1;j<=N;j++)
     if(dist[i][j] > dist[i][k]+dist[k][j])
        dist[i][j]=dist[i][k]+dist[k][j];
          
//formarea retelei de transport
nm1=nm2=0;
for(i=1;i<=N;i++)
  if(gi[i]>go[i])
    m1[++nm1]=i;
  else
  if(gi[i]<go[i])
    m2[++nm2]=i;
     
//sursa - 0, destinatia - nm1+nm2+1
int dest=nm1+nm2+1;
for(i=1;i<=nm1;i++)
  {
  cap[0][i]=gi[ m1[i] ] - go[ m1[i] ];
  cost[0][i]=0;                
  }   
for(i=1;i<=nm2;i++)
  {
  cap[i+nm1][dest]=go[m2[i]]-gi[m2[i]];
  cost[i+nm1][dest]=0;
  }
   
for(i=1;i<=nm1;i++)
 for(j=1;j<=nm2;j++)
   {
   cap[i][j+nm1]=inf;
   cost[i][j+nm1]= dist[m1[i]][m2[j]];                
   cost[j+nm1][i]=-cost[i][j+nm1];                
   }  
    
//fluxu
int val;
 
flux[dest]=1;
while(flux[dest])
{
memset(flux,0,sizeof flux);
flux[0]=inf;
for(i=1;i<=dest;i++)
   cst[i]=inf;
                  
for(k=1;k<=N;k++)
  {                
  for(i=0;i<=dest;i++)
    for(j=0;j<=dest;j++)
      if(cap[i][j])
         {
         val=cap[i][j];
         if(flux[i]<val)
           val=flux[i];
            
         if(val && cst[i]+cost[i][j] <cst[j])
           {
           cst[j]=cst[i]+cost[i][j];
           flux[j]=val;
           ant[j]=i;                  
           }          
         }                    
  }
   
i=dest;
while(i)
  {
  cap[ant[i]][i]-=flux[dest];
  cap[i][ant[i]]+=flux[dest];
   
  i=ant[i];     
  } 
   
sol+=flux[dest]*cst[dest];
}
 
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;        
}