#include<cstdio>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;

#define pb push_back

const char in[]="traseu.in";
const char out[]="traseu.out";

const char Max_N = 65;
const int INF = 0x3f3f3f3f;

bitset<Max_N>in_Q;
vector<int>G[Max_N];
queue<int>Q;

int C[Max_N][Max_N], F[Max_N][Max_N], Cost[Max_N][Max_N];
int grad_In[Max_N], grad_Out[Max_N], dist[Max_N], T[Max_N];
int N, M, S, D;
int x, y, cost, nod;
int sol;

inline int min(int a, int b){return (a > b) ? b : a;}

bool Bellman_Ford()
	{
		in_Q.reset();
		
		while(Q.size())Q.pop();
		
		for(int i = 0 ; i <= D ; ++i)
		{
			dist[i] = INF;
			T[i] = -1;
		}
		
		
		Q.push(S);
		in_Q[S] = true;
		dist[S] = 0;
		
		while(Q.size())
		{
			nod = Q.front();
			Q.pop();
			in_Q[nod] = false;
			for(unsigned i = 0 ; i < G[nod].size() ; ++i)
			{
				x = G[nod][i];
				
				if(dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] - F[nod][x] > 0)
				{
					dist[x] = dist[nod] + Cost[nod][x];
					T[x] = nod;
					if(!in_Q[x])
					{
						Q.push(x);
						in_Q[x] = true;
					}
				}
			}
		}
		
		return (dist[D] != INF);
}



int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		scanf("%d %d", &N, &M);
		
		for(int i = 1 ; i <= M ; ++i)
		{
			scanf("%d %d %d", &x, &y, &cost);
			G[x].pb(y);
			G[y].pb(x);
			
			Cost[x][y] += cost;
			Cost[y][x] -= cost;
			
			C[x][y] = INF;
			
			++grad_In[y];
			++grad_Out[x];
			
			
		}
		
		S = 0;
		D = N + 1;
		
		for(int i = 1 ; i <= N ; ++i)
			if(grad_In[i] < grad_Out[i])
				{
					G[D].pb(i);
					G[i].pb(D);
					C[i][D] = grad_Out[i] - grad_In[i];
			}
			else if(grad_In[i] > grad_Out[i])
			{
				G[S].pb(i);
				G[i].pb(S);
				C[S][i] = grad_In[i] - grad_Out[i];
			}
			
			int min_f;
			
			while(Bellman_Ford())
			{
				min_f = INF;
				
				for(int i = D ; i != S ; i = T[i])
					min_f = min(min_f, C[T[i]][i] - F[T[i]][i]);
				for(int i = D ; i != S ; i = T[i])
				{
					F[T[i]][i] += min_f;
					F[i][T[i]] -= min_f;
				}
				
			sol += min_f * dist[D];
			
			}
			
			printf("%d\n", sol);
			
			return 0;
}