#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];

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;

	for (int i = 1; i <= m; i++) 
    	for (int j = 1; j <= d; j++)
			if (flow[j]) 
				for (int k = 1; k <= d; k++)
					if (C[j][k] > 0 && D[k] > D[j] + cost[j][k]) {
                    	tata[k] = j;
						flow[k] = min(flow[j], C[j][k]);
						D[k] = D[j] + cost[j][k];
					}

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

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] = 1;

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

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