#include<stdio.h>
long int sol,n,m,i,x[3700],y[3700],c[3700],cc[63][63],
k,j,ccc,pol[63],lin,col,cap[63][63],dist[63],pred[63],
viz[63],ok,e,cmin,flow;
void citire();
long int flux();
int main()
{       FILE *g;g=fopen("traseu.out","w");
	citire();
	while(flux());
	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]);
	for(i=1;i<=m;i++) { cc[x[i]][y[i]]=c[i];sol+=c[i];}
	for(k=1;k<=n;k++)for(i=1;i<=n;i++)if(k!=i&&cc[i][k])for(j=1;j<=n;j++)if(k!=j&&i!=j&&cc[k][j]){ ccc=cc[i][k]+cc[k][j];if(!cc[i][j]||cc[i][j]>ccc)cc[i][j]=ccc;}
	for(i=1;i<=m;i++)pol[x[i]]++;
	for(i=1;i<=m;i++)pol[y[i]]--;
	for(i=1;i<=n;i++)
	 { while(!pol[i]&&i<=n)
	   {
		for(lin=i;lin<=n;lin++)for(col=1;col<=n;col++)cc[lin][col]=cc[lin+1][col];
		for(col=i;col<=n;col++)for(lin=1;lin<=n;lin++)cc[lin][col]=cc[lin][col+1];
		for(j=i;j<=n;j++)pol[j]=pol[j+1];
		n--;
	   }
	 }
	for(i=1;i<=n;i++)if(pol[i]<0){cap[0][i]=-pol[i];for(j=1;j<=n;j++)if(pol[j]>0)cap[i][j]=100000000;}
	for(i=1;i<=n;i++)if(pol[i]>0){cap[i][n+1]=pol[i];for(j=1;j<=n;j++)if(pol[j]<0)cc[i][j]=-cc[j][i];}
	n++;
}
long int flux()
{
	dist[0]=0;
	for(i=0;i<=n;i++)
	 { dist[i]=100000000;pred[i]=0;viz[i]=0;}
	dist[0]=0;pred[0]=-1;
	ok=1;
	while(ok)
	{       ok=0;
		e=-1;
		cmin=100000000;
		for(i=0;i<=n;i++)if(dist[i]<cmin)if(!viz[i]){ cmin=dist[i];e=i;}
		if(e>-1)
		 if(e<n){viz[e]=1;ok=1;for(i=0;i<=n;i++)if(!viz[i])if(cap[e][i])if(dist[i]>dist[e]+cc[e][i]){dist[i]=dist[e]+cc[e][i];pred[i]=e;}}
		 if(e==n){flow=10000000;for(k=n;pred[k]>=0;k=pred[k])if(cap[pred[k]][k]<flow)flow=cap[pred[k]][k];for(k=n;pred[k]>=0;k=pred[k]){ cap[pred[k]][k]-=flow;cap[k][pred[k]]+=flow;}
		 sol+=flow*dist[n];
		 return 1;
		}
	}
	return 0;
}