/*
    Problema cuplajului de cost minim a nodurilor cu grad_intrare > grad_iesire
    Complexitate: O(N^4)
*/

#include <stdio.h>

#define infile "traseu.in"
#define outfile "traseu.out"
#define NMAX 61
#define INF 1000000000
struct NOD {int x,c; NOD *adr;};

FILE *fin,*fout;
int suma=0,cost[NMAX][NMAX],grad_in[NMAX],grad_out[NMAX];
int n,n_ini;
int cost_minim=0;
NOD *prim[2*NMAX+2];
short int cap[2*NMAX+2][2*NMAX+2];
short int prec[2*NMAX+2];
int bfcost[2*NMAX+2];

inline void adaug_st(NOD *(&prim), int x, int c)
  {
   NOD *a=new NOD;
   a->x=x;
   a->c=c;
   a->adr=prim;
   prim=a;
  }

void citire_init()
  {
   int i,j,m,u,v,c;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d",&n,&m);
   suma=0;
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         if(i==j)
           cost[i][j]=0;
         else
           cost[i][j]=INF;
   for(i=0;i<n;i++)
      grad_in[i]=grad_out[i]=0;
   for(i=0;i<m;i++)
      {
       fscanf(fin,"%d %d %d",&u,&v,&c);
       u--; v--;
       suma+=c;
       cost[u][v]=c;
       grad_out[u]++;
       grad_in[v]++;
      }
   fclose(fin);
  }

void roy_floyd()
  {
   int i,j,k;
   for(k=0;k<n;k++)
      for(i=0;i<n;i++)
      if(i!=k)
        for(j=0;j<n;j++)
        if(j!=k && j!=i)
          if(cost[i][j] > cost[i][k]+cost[k][j])
            cost[i][j] = cost[i][k]+cost[k][j];
  }

void constr_retea()
  {
   int i,j;
   for(i=0;i<2*n+2;i++)
      prim[i]=NULL;
   for(i=1;i<=n;i++)
      if(grad_in[i-1]>grad_out[i-1])
        {
         cap[0][i]=grad_in[i-1]-grad_out[i-1];
         cap[i][0]=0;
         adaug_st(prim[0],i,0);
         adaug_st(prim[i],0,0);
        }
   for(i=n+1;i<=2*n;i++)
      if(grad_in[i-n-1]<grad_out[i-n-1])
        {
         cap[i][2*n+1]=grad_out[i-n-1]-grad_in[i-n-1];
         cap[2*n+1][i]=0;
         adaug_st(prim[i],2*n+1,0);
         adaug_st(prim[2*n+1],i,0);
        }
   for(i=1;i<=n;i++)
      if(grad_in[i-1]>grad_out[i-1])
        for(j=n+1;j<=2*n;j++)
           if(grad_in[j-n-1]<grad_out[j-n-1])
             {
              cap[i][j]=1;
              cap[j][i]=0;
              adaug_st(prim[i],j,cost[i-1][j-n-1]);
              adaug_st(prim[j],i,-cost[i-1][j-n-1]);
             }
   n_ini=n;
   n=2*n+2;
  }

void bellman_ford()
  {
   int i;
   NOD *b;
   for(i=1;i<n;i++)
      bfcost[i]=INF;
   prec[0]=-1;
   bfcost[0]=0;
   for(i=0;i<n;i++)
      {
       b=prim[i];
       while(b)
            {
             if(cap[i][b->x] && bfcost[b->x]>bfcost[i]+b->c && bfcost[i]!=INF)
               {
                bfcost[b->x]=bfcost[i]+b->c;
                prec[b->x]=i;
               }
             b=b->adr;
            }
      }
  }

void cuplaj()
  {
   int u,v,min;
   do{
      bellman_ford();
      if(bfcost[n-1]!=INF)
        {
         u=prec[n-1];
         v=n-1;
         min=INF;
         while(u!=-1)
              {
               if(min>cap[u][v])
                 min=cap[u][v];
               v=u;
               u=prec[u];
              }
         u=prec[n-1];
         v=n-1;
         while(u!=-1)
              {
               cap[u][v]-=min;
               cap[v][u]+=min;
               v=u;
               u=prec[u];
              }
        }
     }while(bfcost[n-1]!=INF);
  }


int main()
{
int i,j;
citire_init();
roy_floyd();
constr_retea();
cuplaj();

n=n_ini;
cost_minim=0;
for(i=1;i<=n;i++)
   if(grad_in[i-1]>grad_out[i-1])
     for(j=n+1;j<=2*n;j++)
        if(grad_in[j-n-1]<grad_out[j-n-1])
          if(!cap[i][j])
            cost_minim+=cost[i-1][j-n-1];

fout=fopen(outfile,"w");
fprintf(fout,"%d\n",suma+cost_minim);
fclose(fout);
return 0;
}