#include<stdio.h>
long long int n,m,i,xx,yy,cc,gout[62],gin[62],c[62][62],cb,cap[62][62],
cm[62][62],j,infinit,k,delta[62],cost[62][62],mm,ok,dist[62],pred[62],
x[62],y[62],aux,v1,v2,v3,v4,flux;
void flux_max_cmin();
int main()
{
	FILE *f,*g;f=fopen("traseu.in","r");g=fopen("traseu.out","w");
	fscanf(f,"%lld%lld",&n,&m);
	infinit=2000000000;
	for(i=1;i<=m;i++)
	{ fscanf(f,"%lld%lld%lld",&xx,&yy,&cc);
	  c[xx][yy]=cc;gout[xx]++;gin[yy]++;
	  cap[xx][yy]=1;cb+=cc;
	}
	for(i=1;i<=n;i++)
	 for(j=1;j<=n;j++)
	  { if(cap[i][j]) cm[i][j]=c[i][j];
	    else cm[i][j]=infinit;
	  }
	for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(cm[i][k]+cm[k][j]<cm[i][j])cm[i][j]=cm[i][k]+cm[k][j];
	for(i=1;i<=n;i++) delta[i]=gin[i]-gout[i];
	for(i=1;i<=n;i++)
	 {
	    if(delta[i]>0)
	      { cap[0][i]=delta[i];
		mm++;x[mm]=0;y[mm]=i;
		for(j=1;j<=n;j++)
		 if(delta[j]<0)
		  { cap[i][j]=infinit;
		    cost[i][j]=cm[i][j];
		    mm++;x[mm]=i;y[mm]=j;
		  }
	      }
	    if(delta[i]<0)
	     { cap[i][n+1]=-delta[i];
	       mm++;
	       x[mm]=i;y[mm]=j;
	     }
	 }
	flux_max_cmin();
	fprintf(g,"%lld\n",cb);
	fcloseall();
	return 0;
}
void flux_max_cmin()
{
	ok=1;
	while(ok)
	{    ok=0;
	     for(i=1;i<=n+1;i++)
	      { dist[i]=infinit;
		pred[i]=0;
	      }
	     for(j=1;j<=mm;j++)
	      if(cost[x[j]][y[j]]==infinit)
	       { aux=x[mm];x[mm]=x[j];x[j]=aux;
		 aux=y[mm];y[mm]=y[j];y[j]=aux;
		 mm--;
	       }
	      for(i=1;i<=n;i++)
	      for(j=1;j<=mm;j++)
	      { if(dist[y[j]]>dist[x[j]]+cost[x[j]][y[j]])
		{ dist[y[j]]=dist[x[j]]+cost[x[j]][y[j]];
		  pred[y[j]]=x[j];
		}
	      }
	      if(dist[n+1]<infinit)
	      { ok=1;
		v1=0;v2=pred[pred[n+1]];v3=pred[n+1];v4=n+1;
		flux=(cap[v1][v2]<cap[v3][v4])?cap[v1][v2]:cap[v3][v4];
		cb+=cost[v2][v3];
		cap[v1][v2]-=flux;if(!cap[v1][v2])cost[v1][v2]=infinit;
		cap[v3][v4]-=flux;if(!cap[v3][v4])cost[v3][v4]=infinit;
	      }
	}
}