#include<stdio.h>
long int sol,n,m,i,x[3700],y[3700],c[3700],cost[65][65],
k,j,ccc,pol[65],lin,col,cap[6][6],dist[65],pred[65],
viz[65],ok,e,cmin,flow,i8=1000000000,fc,fl[65][65];
void citire();
long int find_path();
void act_flow();
void roy();
int main()
{       FILE *g;g=fopen("traseu.out","w");
	citire();
	while(find_path())
	 act_flow();
	fprintf(g,"%ld\n",sol);
	return 0;
}
void citire()
{
	FILE *f;f=fopen("traseu.in","r");
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;i++)
	 {fscanf(f,"%ld%ld%ld",&x[i],&y[i],&c[i]);cost[x[i]][y[i]]=c[i];sol+=c[i];pol[x[i]]++;pol[y[i]]--;}
	roy();
	for(i=1;i<=n;i++)if(pol[i]<0)cap[0][i]=-pol[i];
	for(i=1;i<=n;i++)if(pol[i]>0)cap[i][n+1]=pol[i];
	for(i=1;i<=n;i++)if(pol[i]<0)for(j=1;j<=n;j++)if(pol[j]>0){ cap[i][j]=i8;cost[j][i]=-cost[i][j];}
}
long int find_path()//Bellman-Ford
{
	long int u,v;
	for(i=0;i<=n+1;i++){ dist[i]=i8;pred[i]=-1;}
	dist[0]=0;
	m=0;
	for(j=0;j<=n+1;j++)
	 for(k=0;k<=n+1;k++)
	  if(cap[j][k]){m++;x[m]=j;y[m]=k;c[m]=cost[j][k];}
	for(i=0;i<=n;i++)
	 for(j=1;j<=m;j++)
	   if(dist[x[j]]<i8)
	    {
	     u=x[j];v=y[j];
	     if(dist[v]>dist[u]+c[j])
	     { dist[v]=dist[u]+c[j];pred[v]=u;}
	   }
	if(pred[n+1]==-1)return 0;
	return 1;
}
void act_flow()
{
     fc=i8;
     for(k=n+1;pred[k]>=0;k=pred[k])
      if(cap[pred[k]][k]<fc)
       fc=cap[pred[k]][k];
     for(k=n+1;pred[k]>=0;k=pred[k])
	{ cap[pred[k]][k]-=fc;cap[k][pred[k]]+=fc;
	  fl[pred[k]][k]+=fc;fl[k][pred[k]]-=fc;
	}
     for(k=n+1;pred[k]>=0;k=pred[k])
	sol+=fc*cost[pred[k]][k];
}
void roy()
{   for(k=1;k<=n;k++)
     for(i=1;i<=n;i++)
      { if(cost[i][k])
	 for(j=1;j<=n;j++)
	 { if(cost[k][j])
	    if(!cost[i][j]||(cost[i][j]>cost[i][k]+cost[k][j]))
	     cost[i][j]=cost[i][k]+cost[k][j];
	 }
      }
}