#include <cstdio>
#include <memory>
using namespace std;

const char iname[] = "traseu.in";
const char oname[] = "traseu.out";

#define MAX_N 61

int N;

int D[MAX_N][MAX_N];

int in_deg[MAX_N], out_deg[MAX_N];

int R;

int C[MAX_N][MAX_N], F[MAX_N][MAX_N], A[MAX_N][MAX_N], X[MAX_N];

int Q[MAX_N * MAX_N], P[MAX_N], V[MAX_N];


inline void add(const int x, const int y) {
	A[x][++A[x][0]] = y;
}

int bellman_ford(const int srs, const int dst)
{
	int head, tail;
	int x, y;
	int i;

	memset(X, 0, sizeof(X));
	memset(V, 1, sizeof(V));
	P[dst] = 0;
	V[srs] = 0;
	X[srs] = MAX_N;
	for (Q[head = tail = 0] = srs; head <= tail; ++head) {
		x = Q[head];
		for (i = A[x][0]; i > 0; --i) {
			y = A[x][i];
			if (C[x][y] - F[x][y] > 0)
				if (V[y] > V[x] + D[x][y]) {
					V[y] = V[x] + D[x][y];
					X[ Q[++tail] = y ] = min(X[x], C[x][y] - F[x][y]);
					P[y] = x;
				}
		}
	}
	if (X[dst] == 0)
		return 0;
	for (x = dst; x != srs; x = P[x])
		F[P[x]][x] += X[dst],
		F[x][P[x]] -= X[dst];

	return 1;
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	int M;
	int i, j, k;
	int x, y;
	
	scanf("%d", & N);
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j)  
			if (i != j)  D[i][j] = int(1e9);
	for (scanf("%d", & M), i = 0; i < M; ++i) {
		scanf("%d %d", & x, & y);
		scanf("%d", D[x] + y);
		R += D[x][y];
		in_deg[y]  += 1;
		out_deg[x] += 1;
	}
	for (k = 1; k <= N; ++k)
		for (i = 1; i <= N; ++i)
			for (j = 1; j <= N; ++j)
				if (D[i][j] > D[i][k] + D[k][j])  D[i][j] = D[i][k] + D[k][j];

	for (i = 1; i <= N; ++i)
		if (in_deg[i] - out_deg[i] > 0)  
			X[i] = -1;
		else if (out_deg[i] - in_deg[i] > 0)  
			X[i] = +1;

	for (i = 1; i <= N; ++i)
		if (X[i] == -1) 
			add(0, i), add(i, 0), C[0][i] = in_deg[i] - out_deg[i];
		else if (X[i] == +1)
			add(i, N + 1), add(N + 1, i), C[i][N + 1] = out_deg[i] - in_deg[i];

	for (i = 1; i <= N; ++i)
		if (X[i] == -1)
			for (j = 1; j <= N; ++j)
				if (X[j] == +1) {
					D[j][i] = - D[i][j];
					add(i, j), add(j, i), C[i][j] = MAX_N;
				}

	while (bellman_ford(0, N + 1))
		;

	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			if (F[i][j] > 0)  R += F[i][j] * D[i][j];

	printf("%d\n", R);

	return 0;
}