#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;


#define NMAX 65
#define INF 0x3f3f3f

int C[NMAX][NMAX],cost[NMAX][NMAX],S,D;
queue <int> q;
int inq[NMAX],d[NMAX],grin[NMAX],grout[NMAX],p[NMAX];
vector <int> v[NMAX];

int bellman_ford()
{
	int nod,i;
	for(i=S;i<=D;i++)
		d[i]=INF;
	memset(inq,0,sizeof(inq));
	memset(p,0,sizeof(p));
	q.push(S);
	inq[S]=1;
	d[S]=0;
	while(q.empty()==0) {
		nod=q.front();
		q.pop();
		inq[nod]=0;
		for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
			if(d[nod]+cost[nod][*it]<d[*it] && C[nod][*it]>=1) {
				d[*it]=d[nod]+cost[nod][*it];
				//if(inq[*it]==0) {
					q.push(*it);
					inq[*it]=1;
					p[*it]=nod;
				//}
			}
	}
	return d[D];
}

	
int main ()
{
	int n,m,i,x,y,sol,len,nod,flow;
	ifstream f("traseu.in");
	ofstream g("traseu.out");
	f>>n>>m;
	sol=0;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		f>>cost[x][y];
		sol=sol+cost[x][y];
		v[x].push_back(y);
		v[y].push_back(x);
		cost[y][x]=-cost[x][y];
		C[x][y]=INF;
		grout[x]++;
		grin[y]++;
	}
	f.close();
	S=0;
	D=n+1;
	for(i=1;i<=n;i++) {
		if(grin[i]<grout[i]) {
			v[i].push_back(D);
			v[D].push_back(i);
			C[i][D]=grout[i]-grin[i];
		}
		if(grin[i]>grout[i]) {
			v[S].push_back(i);
			v[i].push_back(S);
			C[S][i]=grin[i]-grout[i];
		}
	}
	len=bellman_ford();
	while(len!=INF) {
		flow=INF;
		for(nod=D;nod!=S;nod=p[nod]) 
			flow=min(flow,C[p[nod]][nod]);
		for(nod=D;nod!=S;nod=p[nod]) {
			C[p[nod]][nod]-=flow;
			C[nod][p[nod]]+=flow;
		}
		sol=sol+flow*len;
		len=bellman_ford();
	}
	g<<sol;
	g.close();
	return 0;
}