#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 s1[64], s2[64], cnt1, cnt2;

int bf();

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 <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			mat[i][j] = inf;
		}
	}

	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &a, &b, &c);
		++out[a];
		++in[b];
		mat[a][b] = c;
		sol += c;
	}

	for(k = 1; k <= n; ++k)
	{
		for(i = 1; i <= n; ++i)
		{
			for(j = 1; j <= n; ++j)
			{
				if(mat[i][j] > mat[i][k] + mat[k][j])
				{
					mat[i][j] = mat[i][k] + mat[k][j];
				}
			}
		}
	}

	for(i = 1; i <= n; ++i)
	{
		if(in[i] > out[i])
		{
			s1[++cnt1] = i;
			cap[0][i] = in[i] - out[i];
		}
		if(in[i] < out[i])
		{
			s2[++cnt2] = i;
			cap[i][n + 1] = out[i] - in[i];
		}
	}
	for(i = 1; i <= n; ++i)
	{
		for(j = 1; j <= n; ++j)
		{
			cap[i][j] = inf;
			cost[i][j] = mat[i][j];
		}
	}

	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;
}

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] && 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];
}