#include<stdio.h>
long int sol,n,m,i,x[3670],y[3670],c[3670],cost[65][65],
k,j,ccc,pol[65],lin,col,cap[65][65],dist[65],pred[65],
viz[65],ok,e,cmin,flow,i8=100000000,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()
{
	for(i=0;i<=n+1;i++){ dist[i]=i8;pred[i]=0;viz[i]=0;}
	pred[0]=-1;
	ok=1;
	while(ok)
	{ ok=0;e=-1;cmin=i8;
	  for(i=0;i<=n+1;i++)if(dist[i]<cmin&&!viz[i]){cmin=dist[i];e=i;}
	  if(e==n+1) return 1;
	  if(e>-1)
	   { viz[e]=1;
	     ok=1;
	     for(i=0;i<=n+1;i++)if(cap[e][i])if(!viz[i]&&dist[i]>dist[e]+cost[e][i]){dist[i]=dist[e]+cost[e][i];pred[i]=e;}
	   }
	}
	return 0;
}
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;
	}
     sol+=fc*dist[n];
}
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];
	 }
      }
}