#include <cstdio>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define NMAX 64
#define oo 1000000
vector <int> M[NMAX];
int C[NMAX][NMAX], cap[NMAX][NMAX];
int Sum,n,gi[NMAX],go[NMAX],dist[NMAX],s,d,from[NMAX],Q[300];
bool viz[NMAX],gasit;

void citire()
{
	freopen("traseu.in","r",stdin);
	int m;
	scanf("%d %d",&n,&m);
	
	int i,j;
	for (i=1;i<=n;++i)
	 for (j=1;j<=n;++j)
		C[i][j]=oo;
	
	for (i=0;i<m;++i)
	{ int x,y,ct;
		scanf("%d %d %d",&x,&y,&ct);
		C[x][y]=ct;			
		gi[y]++; go[x]++; 
		Sum+=ct;
	}	
}

int Flux()
{
	int x,st,dr; unsigned i;
	for (i=0;i<M[s].size();++i) { dist[M[s][i]]=oo; from[M[s][i]]=-1; }
	for (i=0;i<M[d].size();++i) { dist[M[d][i]]=oo; from[M[d][i]]=-1; }
	memset(viz,0,sizeof(viz));
	dist[d]=oo; from[d]=-1;
	dist[s]=0; viz[s]=1; st=dr=0; Q[0]=s;
	while (st<=dr)
	{
		x=Q[st++]; 
		for (i=0;i<M[x].size();++i)
		 if (cap[x][M[x][i]]>0 && dist[M[x][i]]>dist[x]+C[x][M[x][i]])
		 {
			dist[M[x][i]]=dist[x]+C[x][M[x][i]] ;
			from[M[x][i]]=x;
			if (!viz[M[x][i]])
			{
				viz[M[x][i]]=1;
				Q[++dr]=M[x][i];
			}
		 }		 
		viz[x]=0;
	}
	
	if (from[d]==-1) return 0;
	gasit=1;
	int flux=oo; 
	for (i=d; i!=s; i=from[i]) flux=min(flux,cap[from[i]][i]);
	for (i=d; i!=s; i=from[i]) 
		cap[from[i]][i]-=flux, cap[i][from[i]]+=flux;
	return flux*dist[d];
}

int main()
{ 
	Sum=0;	
	citire();
	
	//drumuri minime
	int x,y,z; 
	unsigned i,j;	
	for (y=1;y<=n;++y)
	 for (x=1;x<=n;++x)
	  for (z=1;z<=n;++z)
		if (C[x][z]>C[x][y]+C[y][z])
			C[x][z]=C[x][y]+C[y][z];
		
	s=0;d=n+1; 
	memset(cap,0,sizeof(cap));
	for (i=1;i<=n;++i)
	{		
		if (gi[i]>go[i]) {M[s].pb(i); M[i].pb(s); C[s][i]=C[i][s]=0; cap[s][i]=gi[i]-go[i];} else
		if (gi[i]<go[i]) {M[d].pb(i); M[i].pb(d); C[d][i]=C[i][d]=0; cap[i][d]=go[i]-gi[i];}
	}

   	for (i=0;i<M[s].size();++i)
	{
	 x=M[s][i];
	 for (j=0;j<M[d].size();++j)
	 {
		y=M[d][j];
		cap[x][y]=oo; C[y][x]=-C[x][y];
		M[x].pb(y); M[y].pb(x);
	 }
	}
	
	do
	{
		gasit=0;
		Sum+=Flux();
	}
	while (gasit);
	
	freopen("traseu.out","w",stdout);
	printf("%d\n",Sum);	
	return 0;
}