#include <fstream>
#include <vector>
#include <queue>
#define NMAx 64
#define oo (1<<30)
#define pb push_back
using namespace std;

queue <short> Q;
vector <short> G[NMAx];
int Cost[NMAx][NMAx],Flux[NMAx][NMAx],dist[NMAx];
int IN[NMAx],OUT[NMAx],in_queue[NMAx],tata[NMAx];
int n,Flow,S,D,color;

bool BellmanFord() {
	
	int i,nod,vecin;
	
	for(i=S;i<=D;i++)
		dist[i]=oo;
	
	Q.push(S);
	dist[S]=0;
	color++;
	
	while(!Q.empty()) {
		
		nod=Q.front();
		Q.pop();
		in_queue[nod]=0;
		
		for(i=0;i<G[nod].size();i++) {
			vecin=G[nod][i];
		
			if(Flux[nod][vecin]>0&&dist[vecin]>dist[nod]+Cost[nod][vecin]) {
				
				dist[vecin]=dist[nod]+Cost[nod][vecin];
				tata[vecin]=nod;
				
				if(in_queue[vecin]!=color) {
					
					in_queue[vecin]=color;
					Q.push(vecin);
					}
				}
			}
		}

	if(dist[D]==oo)
		return 0;
	return 1;
	
}
void constr_flux_network() {
	
	int i;
	
	S=0;
	D=n+1;
	
	for(i=1;i<=n;i++) {
		if(IN[i]>OUT[i]) {
			
			Flux[S][i]=IN[i]-OUT[i];
			G[S].pb(i);
			G[i].pb(S);
			}
		else
		if(OUT[i]>IN[i]) {
			
			Flux[i][D]=OUT[i]-IN[i];
			G[i].pb(D);
			G[D].pb(i);
			}
		}
	
}
void citire() {
	
	int i,x,y,c,m;
	ifstream in("traseu.in");
	in>>n>>m;
	
	for(i=0;i<m;i++) {
		in>>x>>y>>c;
		
		Cost[x][y]=c;
		Cost[y][x]=-c;
		
		G[x].pb(y);
		G[y].pb(x);
		
		IN[y]++;
		OUT[x]++;
		
		Flux[x][y]=oo;
		Flow+=c;
		
		}
	
	in.close();

}
int main() {
	
	int e,nod;
	citire();
	
	constr_flux_network();
	
	while(BellmanFord()) {
		
		e=oo;
		for(nod=D;nod!=S;nod=tata[nod])
			e=min(e,Flux[tata[nod]][nod]);
		
		for(nod=D;nod!=S;nod=tata[nod]) {
			
			Flux[tata[nod]][nod]-=e;
			Flux[nod][tata[nod]]+=e;
			}
		
		Flow+=e*dist[D];
		
		}
	
	ofstream out("traseu.out");
	out<<Flow<<'\n';
	out.close();
	
	return 0;
}