#include<fstream>
#include<vector>
#include<queue>

#define minim(a, b) ((a)<(b)?(a):(b))
#define InFile "traseu.in"
#define OutFile "traseu.out"
#define pb push_back

using namespace std;

const int MaxN = 1 << 6;
const int INF = 0x3f3f3f3f;

int n,m,S,D,ans,gr[MaxN],C[MaxN][MaxN],F[MaxN][MaxN],inQ[MaxN],T[MaxN],d[MaxN],cst[MaxN][MaxN],dist[MaxN][MaxN];
vector<int> G[MaxN];
queue<int> Q;

void Read()
{
	ifstream f ( InFile );
	f >> n >> m;
	int i,x,y,z;
	memset(dist,INF,sizeof(dist));
	for( i = 0 ; i < m ; i++ )
		{
			f >> x >> y >> z;
			dist[x][y] = z;
			gr[x]--;
			gr[y]++;
			ans += z;
		}
	f.close();
}

void Roy_Floyd()
{
	int i,j,k;
	for( k = 1 ; k <= n ; k++ )
		for( i = 1 ; i <= n ; i++ )
			for( j = 1 ; j <= n ; j++ )
				dist[i][j] = minim(dist[i][j], dist[i][k] + dist[k][j] );
}

void Build()
{
	S = n+1;
	D = n+2;
	int i,j;
	for( i = 1 ; i <= n ; i++ )
		if( gr[i] > 0 )
			{
				C[S][i] = gr[i];
				G[S].pb(i);
				G[i].pb(S);
			}
			else
			if( gr[i] < 0 )
				{
					C[i][D] = -gr[i];
					G[i].pb(D);
					G[D].pb(i);
				}
	for( i = 1 ; i <= n ; i++ )
		if( gr[i] > 0 )
			for( j = 1 ; j <= n ; j++ )
				if( gr[j] < 0 )
					{
						cst[i][j] = dist[i][j];
						cst[j][i] = -dist[i][j];
						C[i][j] = INF;
						G[i].pb(j);
						G[j].pb(i);
					}
}

int Bellman_Ford(int S,int D)
{
	int nod;
	vector<int>::iterator it;
	memset(inQ,0,sizeof(inQ));
	memset(T,0,sizeof(T));
	memset(d,INF,sizeof(d));
	inQ[S] = 1;
	d[S] = 0;
	Q.push(S);
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			inQ[nod] = 0;
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( F[nod][*it] < C[nod][*it] && d[*it] > d[nod] + cst[nod][*it] )
					{
						d[*it] = d[nod] + cst[nod][*it];
						T[*it] = nod;
						if( !inQ[*it] )
							{
								inQ[*it] = 1;
								Q.push(*it);
							}
					}
		}
	return d[D]<INF;
}

void Flux()
{
	while( Bellman_Ford(S,D) )
		{
			int flux,nod;
			flux = INF;
			for( nod = D ; nod != S ; nod = T[nod] )
				flux = minim(flux,C[T[nod]][nod] -F[T[nod]][nod] );
			for( nod = D ; nod != S ; nod = T[nod] )
				{
					F[T[nod]][nod] += flux;
					F[nod][T[nod]] -= flux;
				}
			ans += (flux*d[D]);
		}
}

void write()
{
	ofstream g ( OutFile );
	g << ans << '\n';
	g.close();
}

int main()
{
	Read();
	Roy_Floyd();
	Build();
	Flux();
	write();
	return 0;
}