#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 65;
const int INF = 0x3f3f3f3f;
int v[N], S, D, n, m, CMIN[N][N], f[N][N], c[N][N], Cost[N][N], b[N][N], a[N][N], din[N], dout[N], lin[N], lout[N], di, dt;
queue<int> q;

int BELLMAN_FORD() {
	int i, j, r, k, t[N], C[N];
	for(i = 0; i <= n + 1; ++i) {
		v[i] = 0;
		t[i] = 0;
		C[i] = INF;
	}

	C[S] = 0;
	v[S] = 1;
	q.push(S);
	while(!q.empty()) {
		k = q.front();
		for(i = 0; i <= n + 1; ++i)
			if(a[k][i] && f[k][i] < c[k][i] && C[k] + Cost[k][i] < C[i]) {
				C[i] = C[k] + Cost[k][i];
				t[i] = k;
				if(!v[i]) {
					v[i] = 1;
					q.push(i);
				}
			}
		v[k] = 0;
		q.pop();
	}

	if(C[D] != INF) {
		r = INF;
		k = D;
		while(k != S) {
			r = min(r, c[t[k]][k] - f[t[k]][k]);
			k = t[k];
		}

		k = D;

		while(k != S) {
			f[k][t[k]] -= r;
			f[t[k]][k] += r;
			k = t[k];
		}

		return C[D] * r;
	}

	return 0;
}



int main() {
	freopen("traseu.in", "r", stdin);
	freopen("traseu.out", "w", stdout);
	int INIT = 0;
	int i, x, y ,C, j, k;
	scanf("%d %d", &n, &m);
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			CMIN[i][j] = INF;
	for(i = 1; i <= m; ++i){
		scanf("%d %d %d", &x, &y, &C);
			b[x][y] = CMIN[x][y] = C;
			din[y]++;
			dout[x]++;
			INIT = INIT + C;
	}
	
	for(k = 1; k <= n; ++k) 
		for(i = 1; i <= n; ++i)
			for(j = 1; j <= n; ++j)
				CMIN[i][j] = min(CMIN[i][j], CMIN[i][k] + CMIN[k][j]);
	
	for(i = 1; i <= n; ++i)
		if(din[i] < dout[i]) 
			lin[++di] = i;
		else
			if(din[i] > dout[i])
				lout[++dt] = i;
	
	for(i = 1; i <= di; ++i)
		a[lin[i]][n + 1] = 1, a[n + 1][lin[i]], c[lin[i]][n + 1] =  dout[lin[i]] - din[lin[i]], Cost[lin[i]][n + 1] = 0;
//	printf("\n");

	for(i = 1; i <= dt; ++i)
		a[0][lout[i]] = 1, a[lout[i]][0] = 1,  c[0][lout[i]] = din[lout[i]] - dout[lout[i]], Cost[0][lout[i]] = 0;
//	printf("\n");
	
	for(i = 1; i <= dt; ++i)
		for(j = 1; j <= di; ++j)
			a[lout[i]][lin[j]] = 1, a[lin[j]][lout[i]] = 1, c[lout[i]][lin[j]] = 1000000, Cost[lout[i]][lin[j]] = CMIN[lout[i]][lin[j]], Cost[lin[j]][lout[i]] = - CMIN[lout[i]][lin[j]];
	S = 0;
	D = n + 1;/*
	for(i = 0; i <= n + 1; ++i) {
		for(j = 0; j <= n + 1; ++j)
			printf("%d ", Cost[i][j]);
		printf("\n");
	}
	*/
	int X = 1;
	long long cost = 0;
	
	
	while(X) {
		X = BELLMAN_FORD();
		INIT += X;
	}

	printf("%d\n", INIT);
	
	return 0;
}