#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

#define lg 65
#define pb push_back

int n, m, x, y, z, d[lg][lg], cp[lg][lg], dr[lg], st[lg], in[lg], out[lg], cnt[lg], prd[lg], cost, rez, i, j, k;
vector<int> v[lg];

int find(){
	int x, i, mn = 0x3f3f3f3f;

	bool fst[lg] = {0};

	memset(cnt, 0x3f, sizeof(cnt));
	memset(prd, 0xff, sizeof(prd));

	queue<int> q;
	q.push(0);
	cnt[0] = 0; fst[0] = 1;

	while (!q.empty()){
		x = q.front(), q.pop();
		//printf("  %d\n", x);
		for (i = 0; i < (int)v[x].size(); i ++)
			if (cp[x][v[x][i]] > 0 && cnt[x] + d[x][v[x][i]] < cnt[v[x][i]]){
				cnt[v[x][i]] = cnt[x] + d[x][v[x][i]];
				prd[v[x][i]] = x;

				if (!fst[v[x][i]]){
					fst[v[x][i]] = 1;
					q.push(v[x][i]);
				}
			}
		fst[x] = 0;
	}

	for (x = n+1; prd[x] != -1; x = prd[x])
		mn = min(mn, cp[prd[x]][x]);

	if (mn == 0x3f3f3f3f)
		return 0;

	cost += mn * cnt[n+1];
	for (x = n+1; prd[x] != -1; x = prd[x]){
		cp[prd[x]][x] -= mn;
		cp[x][prd[x]] += mn;

		d[x][prd[x]] = -d[prd[x]][x];
	}

	return 1;
}

int main()
{
	freopen("traseu.in", "rt", stdin);
	freopen("traseu.out", "wt", stdout);

	memset(d, 0x3f, sizeof(d));

	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i ++){
		scanf("%d%d%d", &x, &y, &z);

		rez += z;
		d[x][y] = z;
		out[x] ++, in[y] ++;
	}

	for (i = 1; i <= n; i ++){
		d[0][i] = d[i][n+1] = 0;

		if (in[i] < out[i]){
			st[++ st[0]] = i;

			v[i].pb(n+1); v[n+1].pb(i);
			cp[i][n+1] = out[i] - in[i];
		}
		else
			if (in[i] > out[i]){
				dr[++ dr[0]] = i;

				v[i].pb(0); v[0].pb(i);
				cp[0][i] = in[i] - out[i];
			}
	}

/*	for (i = 1; i <= st[0]; i ++)
		printf("%d\n", st[i]);
	for (i = 1; i <= dr[0]; i ++)
		printf(" %d\n", dr[i]);
*/

	for (k = 1; k <= n; k ++)
		for (i = 1; i <= n; i ++)
			for (j = 1; j <= n; j ++)
				if (i != j)
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

	for (i = 1; i <= dr[0]; i ++){
		j = dr[i];

		for (k = 1; k <= st[0]; k ++){
			v[j].pb(st[k]);
			v[st[k]].pb(j);

			cp[j][st[k]] = 0x3f3f3f3f;
		}
	}

	do
		x = find();
	while (x);

	printf("%d\n", cost + rez);

	return 0;
}