#include <stdio.h>
const int inf = 1000000000;
int mat[64][64], in[64], out[64], n, m, cap[64][64], cost[64][64], prev[64], sol;
int bf()
{
	int q[64 * 64], st, dr, d[64], used[64], i, nod;

	for(i = 1; i <= n + 1; ++i)
	{
		d[i] = inf;
		used[i] = 0;
	}
	d[0] = 0;
	q[st = dr = 1] = 0;
	while(st <= dr)
	{
		nod = q[st];
		used[nod] = 0;

		for(i = 1; i <= n + 1; ++i)
		{
			if(cap[nod][i] > 0 && d[i] > d[nod] + cost[nod][i])
			{
				d[i] = d[nod] + cost[nod][i];
				prev[i] = nod;
				if(!used[i])
				{
					q[++dr] = i;
					used[i] = 1;
				}
			}
		}
		++st;
	}
	if(d[n + 1] == inf)
		return 0;
	return d[n + 1];
}
int main()
{
	freopen("traseu.in", "r", stdin);
	freopen("traseu.out", "w", stdout);
	int i, j, k, a, b, c, temp, min_cap, nod;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &a, &b, &c);
		++out[a];
		++in[b];
		cost[a][b] = c;
		cost[b][a] = -c;
		cap[a][b] = inf;
		sol += c;
	}
	for(i = 1; i <= n; ++i)
	{
		if(in[i] > out[i])
		{
			cap[0][i] = in[i] - out[i];
		}
		if(in[i] < out[i])
		{
			cap[i][n + 1] = out[i] - in[i];
		}
	}
	while(temp = bf())
	{
		min_cap = inf;
		for(nod = n + 1; nod; nod = prev[nod])
		{
			if(cap[prev[nod]][nod] < min_cap)
			{
				min_cap = cap[prev[nod]][nod];
			}
		}
		for(nod = n + 1; nod; nod = prev[nod])
		{
			cap[prev[nod]][nod] -= min_cap;
			cap[nod][prev[nod]] += min_cap;
		}
		sol += temp * min_cap;
	}
	printf("%d\n", sol);
	return 0;
}