#include <stdio.h>
#define maxn 100
#define INF 10000001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)

int N, M;
int gi[maxn], ge[maxn], t[maxn], s[maxn], d[maxn];
int a[maxn][maxn], f[maxn][maxn], c[maxn][maxn], m[maxn][maxn];
FILE *fin = fopen("traseu.in", "rt"), *fout = fopen("traseu.out", "wt");

int bellman()
{
	int nr, i, j, k, ok;
	FOR(i, 0, N+1) d[i] = INF;
	d[0] = 0;
	for (ok = nr = 1; nr < N && ok; nr++)
		for (ok = i = 0; i <= N + 1; i++)
			for(j = 0; j <= N + 1; j++)
				if (i != j && m[i][j])
				{
					if (c[i][j] > f[i][j] && d[j] > d[i] + a[i][j])
					{
						d[j] = d[i] + a[i][j];
						t[j] = i;
						ok = 1;
					}
					if (c[j][i] > f[j][i] && d[i] > d[j] - a[i][j])
					{
						d[i] = d[j] - a[i][j];
						t[i] = j;
						ok = 1;
					}
					//fprintf(fout, "%d %d %d %d %d\n", i, j, d[i], d[j], a[i][j]);
				}

/* FOR(i, 0, N+1)
	fprintf(fout, "%d ", d[i]);
	fprintf(fout, "\n");*/
//	return 0;
	return d[N+1] != INF;

}

int main()
{
	int x, y, ct, i, j, k, tcost = 0;
	fscanf(fin, "%d %d", &N, &M);
	FOR(i, 1, M)
	{
		fscanf(fin, "%d %d %d", &x, &y, &ct);
		a[x][y] = ct;
		c[x][y] = INF;
		m[x][y] = 1;
		ge[x]++, gi[y]++;
		tcost += ct;
	}
	FOR(i, 0, N+1) FOR(j, 0, N+1)
		if (!a[i][j]) a[i][j] = INF;
	
	FOR(k, 1, N)
		FOR(i, 1, N)
			FOR(j, 1, N)
				if (i != j && a[i][j] > a[i][k] + a[k][j])
					a[i][j] = a[i][k] + a[k][j];
	
	FOR(i, 1, N)
	{
		if (gi[i] > ge[i]) c[0][i] = gi[i] - ge[i], a[0][i] = 0, m[0][i] = 1;
		if (ge[i] > gi[i]) c[i][N+1] = ge[i] - gi[i], a[i][N+1] = 0, m[i][N+1] = 1;
	}

	int flux = 0, r;

	for (flux = 0; bellman(); flux += r, tcost += r*d[N+1])
	{
		r = INF;
		for(i = N+1; i != 0; i = t[i])
			if (r > c[t[i]][i] - f[t[i]][i]) 
				r = c[t[i]][i] - f[t[i]][i];
		for (i = N+1; i != 0; i = t[i])
			f[t[i]][i] += r, 
			f[i][t[i]] -= r;
//		fprintf(fout, "%d\n", r);
	}
/*	FOR(i, 0, N+1)
	{
		FOR(j, 0, N+1)
			fprintf(fout, "%d ", a[i][j]);
		fprintf(fout, "\n");
	}*/
	fprintf(fout, "%d\n", tcost);
	fclose(fin), fclose(fout);
	return 0;
}