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

using namespace std;

#define MAX_N 125
#define inf 1000000000

int n, m, s, d, sol;

int in[MAX_N], out[MAX_N], tata[MAX_N], flow[MAX_N], D[MAX_N], Q[MAX_N], inQ[MAX_N];

int dist[MAX_N][MAX_N];

int C[MAX_N][MAX_N], cost[MAX_N][MAX_N];

vector <pair <int, int> > G[MAX_N];

int bf() {
	flow[s] = inf; D[s] = 0;

	int st = 0, dr = 1; Q[dr] = s;	

	while (st < dr) {
    	int nod = Q[++st];

		for (int i = 1; i <= d; i++)
			if (C[nod][i] > 0 && D[i] > D[nod] + cost[nod][i]) {
            	tata[i] = nod;
				flow[i] = min(flow[nod], C[nod][i]);
				D[i] = D[nod] + cost[nod][i];
	
				if (inQ[i] == 0) {
                	Q[++dr] = i;
					inQ[i] = 1;
				}
			}

		inQ[nod] = 0;
	}

	if (flow[d] == 0)
		return 0;
	
	for (int i = d; i != s; i = tata[i]) {
		C[tata[i]][i] -= flow[d];
		C[i][tata[i]] += flow[d];
	}

	return D[d] * flow[d];
}

void solve() {
	memset(dist, 63, sizeof(dist));

	for (int i = 1; i <= n; i++)
		for (vector <pair <int, int> >::iterator it = G[i].begin(); it != G[i].end(); ++it)
			dist[i][it->first] = min(dist[i][it->first], it->second);

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	s = 2 * n + 1; d = 2 * n + 2;
	for (int i = 1; i <= n; i++) {
		C[s][i] = in[i] - out[i];
    	C[i + n][d] = out[i] - in[i];
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cost[i][j + n] = dist[i][j];
            C[i][j + n] = inf;

			cost[j + n][i] = -dist[i][j];
		}

	int improve = 1;

	while (improve) {
		memset(tata, 0, sizeof(tata));
		memset(flow, 0, sizeof(flow));
		memset(D, 63, sizeof(D));
		memset(inQ, 0, sizeof(inQ));

		sol += (improve = bf());
	}

	printf("%d\n", sol);
}

int main() {
	
	freopen("traseu.in", "r", stdin);
	freopen("traseu.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++) {
		int x, y, cost;
                
		scanf("%d %d %d", &x, &y, &cost);
		G[x].push_back(make_pair(y, cost));

		in[y]++; out[x]++;

		sol += cost;
	}

	solve();

	return 0;
}