#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 64
#define INF 0x3f3f3f3f
#define pb push_back

int Cost[NMAX][NMAX], C[NMAX][NMAX], F[NMAX][NMAX], Int[NMAX], Ext[NMAX], T[NMAX], Dist[NMAX];
int N, M, i, x, y, cost, S, D, CostMin, Nod, FluxCt;
vector< int > G[NMAX];
bool Used[NMAX];

inline bool BF()
{
	memset( T, 0, sizeof(T) );
	memset( Dist, INF, sizeof(Dist) );
	Dist[S] = 0;
	memset( Used, false, sizeof(Used) );
	queue< int > Q;
	Q.push( S );
	Used[S] = true;
	
	while( !Q.empty() )
	{
		Nod = Q.front();
		Q.pop();
		Used[Nod] = false;
		
		for( vector< int >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
			if( F[Nod][*it] < C[Nod][*it] && Dist[*it] > Dist[Nod] + Cost[Nod][*it] )
			{
				Dist[*it] = Dist[Nod] + Cost[Nod][*it];
				T[*it] = Nod;
				if( !Used[*it] )
				{
					Used[*it] = true;
					Q.push( *it );
				}
			}
	}
	
	return ( T[D] != 0 );
}

int main()
{
	freopen("traseu.in", "r", stdin);
	freopen("traseu.out", "w", stdout);
	
	scanf("%d%d", &N, &M );
	memset( C, 0, sizeof(C) );
	memset( F, 0, sizeof(F) );
	for( ; M--; )
	{
		scanf("%d%d%d", &x, &y, &cost );
		++Int[y], ++Ext[x];
		C[x][y] = INF;
		Cost[x][y] = cost;
		Cost[y][x] = -cost;
		G[x].pb( y );
		G[y].pb( x );
		
		CostMin += cost;
	}
	
	S = 0, D = N + 1;
	for( i = 1; i <= N; ++i )
		if( Int[i] > Ext[i] )
		{
			G[S].pb( i );
			G[i].pb( S );
			C[S][i] = Int[i] - Ext[i];
		}
		else if( Ext[i] > Int[i] )
		{
			G[D].pb( i );
			G[i].pb( D );
			C[i][D] = Ext[i] - Int[i];
		}
	
	while( BF() )
	{
		FluxCt = INF;
		for( Nod = D; Nod != S; Nod = T[Nod] )
			FluxCt = min( FluxCt, C[ T[Nod] ][Nod] - F[ T[Nod] ][Nod] );
		if( !FluxCt ) continue;
		for( Nod = D; Nod != S; Nod = T[Nod] )
			F[ T[Nod] ][Nod] += FluxCt, F[Nod][ T[Nod] ] -= FluxCt;
		CostMin += FluxCt * Dist[D];
	}
	
	printf("%d\n", CostMin );
	
	return 0;
}