#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>

#define dim 64
#define inf 0x3f3f3f3f

using namespace std;

int degi[dim], dego[dim], x[dim][dim], st[dim], dr[dim], cap[dim][dim], f[dim][dim], dmin[dim][dim], d[dim], t[dim];
int n, m, src, dest, ret;

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

struct Comp
{
	bool operator()(int i, int j)
	{	return d[i] > d[j];
	}
};

vector <int> g[dim], gg[dim];
priority_queue <int, vector <int>, Comp> pq;
queue <int> q;

bool Bellman();
inline int Min(int i, int j)
{	return i < j ? i : j;
}

void ReadData()
{
	freopen(in, "rt", stdin);
	
	int i, a, b, c;
	
	for(scanf("%d %d", &n, &m), i=1; i<=m; ++i)
	{
		scanf("%d %d %d", &a, &b, &c);
		
		x[a][b] = c;
		
		ret += c;
		
		++ degi[b];
		++ dego[a];
		
		g[a].push_back(b);
	}
	
	fclose(stdin);
}

void Dijkstra(int s)
{
	memset(d, inf, sizeof(d));
	pq.push(s);
	
	vector <int> :: iterator it;

	for(it=g[s].begin(); it!=g[s].end(); ++it)
		d[*it] = x[s][*it];
	
	while(pq.empty() == false)
	{
		int nd = pq.top();
		pq.pop();
		
		for(it=g[nd].begin(); it!=g[nd].end(); ++it)
			if(d[*it] > d[nd] + x[nd][*it])
			{
				d[*it] = d[nd] + x[nd][*it];
				pq.push(*it);
			}
	}
	
	memcpy(dmin[s], d, sizeof(d));
}

void BuildNetwork()
{
	src = 0;
	dest = n + 1;
	
	int i, j;
	
	for(i=1; i<=n; ++i)
	{
		if(degi[i] > dego[i])
		{
			gg[src].push_back(i);
			gg[i].push_back(src);
			st[++st[0]] = i;
			cap[src][i] = degi[i] - dego[i];
		}
		if(degi[i] < dego[i])
		{
			gg[i].push_back(dest);
			gg[dest].push_back(i);
			dr[++dr[0]] = i;
			cap[i][dest] = dego[i] - degi[i];
		}
		
		Dijkstra(i);
	}
	
	memset(x, 0, sizeof(x));
	
	for(i=1; i<=st[0]; ++i)
		for(j=1; j<=dr[0]; ++j)
		{
			x[st[i]][dr[j]] = dmin[st[i]][dr[j]];
			x[dr[j]][st[i]] = -dmin[st[i]][dr[j]];
			
			cap[st[i]][dr[j]] = inf;
			gg[st[i]].push_back(dr[j]);
			gg[dr[j]].push_back(st[i]);
		}
}

void Flow()
{
	while(Bellman())
	{
		int i, j, r;
		
//		for(i=1; i<=n; ++i)
//		{
//			if(f[i][dest] < cap[i][dest])
//			{
//				r = cap[i][dest] - f[i][dest];
		
				r = inf;
			
				for(j=dest; j!=0; j=t[j])
					r = Min(r, cap[t[j]][j]-f[t[j]][j]);
					
//				if(!r) continue;
	
				if(r) {
				
//				f[i][dest] += r;
//				f[dest][i] -= r;
				
				for(j=dest; j!=0; j=t[j])
					f[t[j]][j] += r, f[j][t[j]] -= r;
					
//				ret += r * d[dest];
				
				}
			}
//	}
}

void WriteData()
{
	freopen(out, "wt", stdout);
	
	int i, j;
	for(i=1; i<=st[0]; ++i)
		for(j=1; j<=dr[0]; ++j)
			ret += x[st[i]][dr[j]] * f[st[i]][dr[j]];
			
	printf("%d", ret);
	
	fclose(stdout);
}

bool Bellman()
{
	memset(d, inf, sizeof(d));
	memset(t, 0, sizeof(t));
	q.push(src);
	d[src] = 0;
	
	while(q.empty() == false)
	{
		int nd = q.front();
		q.pop();
		
		vector <int> :: iterator it;
		
		for(it=gg[nd].begin(); it!=gg[nd].end(); ++it)
			if(f[nd][*it] < cap[nd][*it] && d[*it] > d[nd] + x[nd][*it])
			{
				d[*it] = d[nd] + x[nd][*it];
				t[*it] = nd;
				q.push(*it);
			}
	}
	
	return t[dest] != 0;
}

int main()
{
	ReadData();
	BuildNetwork();
	Flow();
	WriteData();
	
	return 0;
}