using namespace std;
#include<fstream>
#include<stdio.h>
#define Nmax 64
#define inf 1000000000

int dist[Nmax][Nmax];
int gi[Nmax],go[Nmax];

int cap[Nmax][Nmax],cost[Nmax][Nmax];
int m1[Nmax],m2[Nmax],nm1,nm2;

int flux[Nmax],cst[Nmax],ant[Nmax];

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;         
}