#include<stdio.h>
#include<vector>
#include<queue>

#define maxn 70
#define pb push_back

using namespace std;

FILE*f=fopen("traseu.in","r");
FILE*g=fopen("traseu.out","w");

int n,m,S,D,sol;
int gr_in[maxn],gr_out[maxn];
int left[maxn],right[maxn],Cp[maxn][maxn],F[maxn][maxn],cost[maxn][maxn],dist[maxn],T[maxn];
int inQ[maxn];
vector<int>G[maxn];
queue<int>Q;
const int INF = 1<<28;

inline int min ( const int &a , const int &b ){
	return a <= b ? a : b;
}

inline void init_inf () {
	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= n ; ++j ){
			cost[i][j] = INF;
		}
	}
}

inline void roy_floyd () {
	
	for ( int k = 1 ; k <= n ; ++k ){
		for ( int i = 1 ; i <= n ; ++i ){
			if ( i == k )	continue ;
			for ( int j = 1 ; j <= n ; ++j ){
				if ( j != k && cost[i][k] + cost[k][j] < cost[i][j] ){
					cost[i][j] = cost[i][k] + cost[k][j];
				}
			}
		}
	}
}

inline void build_graph () {
	S = n+1; D = n+2;
	
	for ( int i = 1 ; i <= n ; ++i ){
		if ( gr_in[i] > gr_out[i] ){
			left[i] = 1;
			G[S].pb(i);	G[i].pb(S);
			Cp[S][i] = gr_in[i] - gr_out[i];
		}
		else{
			if ( gr_in[i] < gr_out[i] ){
				right[i] = 1;
				G[i].pb(D); G[D].pb(i);
				Cp[i][D] = gr_out[i] - gr_in[i];
			}
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= n ; ++j ){
			
			if ( left[i] && right[j] ){
				G[i].pb(j); G[j].pb(i);
				Cp[i][j] = INF;
				cost[j][i] = -cost[i][j];
			}
		}
	}
}

inline void init_BF () {
	
	for ( int i = 1 ; i <= D ; ++i ){
		dist[i] = INF;
		inQ[i] = 0;
	}
	Q.push(S); inQ[S] = 1;
	dist[S] = 0;
}

inline bool Bellman_Ford () {
	init_BF();
	
	while ( !Q.empty() ) {
		int nod = Q.front(); Q.pop(); inQ[nod] = 0;
		
		for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int nodvcn = (*itt);
			
			if ( dist[nodvcn] > dist[nod] + cost[nod][nodvcn] && Cp[nod][nodvcn] > F[nod][nodvcn] ){
				dist[nodvcn] = dist[nod] + cost[nod][nodvcn];
				T[nodvcn] = nod;
				
				if ( !inQ[nodvcn] ){
					Q.push(nodvcn); inQ[nodvcn] = 1;
				}
			}
		}
	}
	
	return dist[D] != INF;
}

inline void flux () {
	int nod,now,c = 0;
	
	while ( Bellman_Ford() ){
		
		nod = D,now = INF;
		while ( T[nod] ){
			now = min(now,Cp[T[nod]][nod]-F[T[nod]][nod]);
			nod = T[nod];
		}
		
		nod = D;
		while ( T[nod] ){
			F[T[nod]][nod] += now;
			F[nod][T[nod]] -= now;
			nod = T[nod];
		}
		
		c += now * dist[D];
	}
	
	sol += c;
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	int x,y,c;
	init_inf();
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&c);
		++gr_in[y]; ++gr_out[x];
		cost[x][y] = c; sol += c;
	}
	
	roy_floyd();
	build_graph();
	flux();
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}