#include <stdio.h>
#include <string.h>

#define Nmax 63
#define infinit 10000000

int S=0, D, N, M, x, y, d, i, j, k, g[Nmax][Nmax], f[Nmax][Nmax], cost[Nmax], parinte[Nmax], in[Nmax], out[Nmax];
long long REZULTAT=0;

void read_data()
{
freopen("traseu.in","r",stdin);
scanf("%d %d",&N,&M);
for (i=0;i<M;++i)
    {
    scanf("%d %d %d",&x,&y,&d);
    if ((g[x][y]==0)||(g[x][y]>d))
      	{
         g[x][y]=d;
         g[y][x]=-d;
        }
    ++out[x];
    ++in[y];
    REZULTAT+=d;
    }
fclose(stdin);
D=N+1;
}

void build_flow_network()
{
//leg de sursa S si destinatie D
for (i=1;i<=N;++i)
    if (in[i]-out[i]>0) f[S][i]=in[i]-out[i];
       else if (out[i]-in[i]>0) f[i][D]=out[i]-in[i];
//leg nodurile intre ele
for (i=1;i<=N;++i)
       for (j=1;j<=N;++j)
           if ((g[i][j]>0))
               f[i][j]=infinit;
}

int bellman_ford()
{
int dmin=infinit;
for (i=1;i<=D;++i)
   	cost[i]=infinit;
cost[S]=0;
parinte[S]=0;
for (i=S;i<=D;++i)
    for (j=S;j<=D;++j)
        for (k=S;k<=D;++k)
            if ((f[j][k]!=0)&&(cost[j]!=infinit)&&(cost[k]>cost[j]+g[j][k]))
               {
               cost[k]=cost[j]+g[j][k];
               parinte[k]=j;
               }
return cost[D];
}

void max_flow_min_cost()
{
int dmin,p,cmin;
while ((dmin=bellman_ford())!=infinit)
      {
       p=D;
       cmin=infinit;
       while (p!=0)
             {
             if (f[parinte[p]][p]<cmin) cmin=f[parinte[p]][p];
             p=parinte[p];
             }
      p=D;
      while (p!=0)
            {
            REZULTAT+=g[parinte[p]][p]*cmin;
            f[parinte[p]][p]-=cmin;
            f[p][parinte[p]]+=cmin;
            p=parinte[p];
            }
      }
}

int main()
{
read_data();
build_flow_network();
max_flow_min_cost();
freopen("traseu.out","w",stdout);
printf("%lld",REZULTAT);
fclose(stdout);
return 0;
}