#include <cstdio>
#include <climits>
#include <queue>
using namespace std;

const int INF = INT_MAX;
const int MAX_N = 64;

int Adj[MAX_N][MAX_N], Deg[MAX_N], Left[MAX_N], Right[MAX_N];
int Cap[2 * MAX_N][2 * MAX_N], Cost[2 * MAX_N][2 * MAX_N];
int From[2 * MAX_N], Dist[2 * MAX_N], InQueue[2 * MAX_N];
int m, n;

void bellmanFord(int src, int snk) {
	queue<int> Queue;

	int i, cur;
	for (i = 0; i <= snk; ++ i) {
		InQueue[i] = false;
		From[i] = -1;
		Dist[i] = INF;
	}
	Dist[src] = 0;
	InQueue[src] = true;
	Queue.push(src);

	while (Queue.empty() == false) {
		cur = Queue.front();
		Queue.pop();
		InQueue[cur] = false;

		for (i = 0; i <= snk; ++ i)
			if (Cap[cur][i] > 0 && Dist[cur] + Cost[cur][i] < Dist[i]) {
				From[i] = cur;
				Dist[i] = Dist[cur] + Cost[cur][i];
				if (InQueue[i] == false) {
					Queue.push(i);
					InQueue[i] = true;
				}
			}
	}
}

int pathCapacity(int src, int snk) {
	bellmanFord(src, snk);

	int cur, cap = INF;
	for (cur = snk; From[cur] != -1; cur = From[cur])
		cap = min(cap, Cap[From[cur]][cur]);
	
	if (cap == INF)
		return 0;
	
	for (cur = snk; From[cur] != -1; cur = From[cur]) {
		Cap[From[cur]][cur] -= cap;
		Cap[cur][From[cur]] += cap;
	}
	
	return cap;
}

int maxFlow(int src, int snk) {
	int ans = 0, cur = pathCapacity(src, snk);
	ans += Dist[snk];
	for (; cur != 0; cur = pathCapacity(src, snk))
		ans += Dist[snk];

	return ans;
}

void floydWarshall() {
	int i, j, k;
	for (k = 1; k <= n; ++ k)
		for (i = 1; i <= n; ++ i)
			for (j = 1; j <= n; ++ j) {
				if (Adj[i][k] == INF || Adj[k][j] == INF)
					continue;
				if (Adj[i][j] > Adj[i][k] + Adj[k][j])
					Adj[i][j] = Adj[i][k] + Adj[k][j];
			}
}

int main() {

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

	scanf("%d %d", &n, &m);
	int i, j;
	for (i = 1; i <= n; ++ i)
		for (j = 1; j <= n; ++ j)
			Adj[i][j] = INF;
	int v1, v2, c, ans = 0;
	for (i = 0; i < m; ++ i) {
		scanf("%d %d %d", &v1, &v2, &c);
		Adj[v1][v2] = c;
		ans += c;
	}

	for (i = 1; i <= n; ++ i) {
		for (j = 1; j <= n; ++ j)
			if (Adj[i][j] != INF) {
				-- Deg[i];
				++ Deg[j];
			}
	}
	floydWarshall();

	for (i = 1, Left[0] = 0, Right[0] = 0; i <= n; ++ i) {
		if (Deg[i] > 0)
			Left[++ Left[0]] = i;
		if (Deg[i] < 0)
			Right[++ Right[0]] = i;
	}

	for (i = 1; i <= Left[0]; ++ i)
		for (j = 1; j <= Right[0]; ++ j) {
			Cost[i][j + Left[0]] = Adj[Left[i]][Right[j]];
			Cost[j + Left[0]][i] = Adj[Left[i]][Right[j]];
			Cap[i][j + Left[0]] = INF;
		}
	for (i = 1; i <= Left[0]; ++ i)
		Cap[0][i] = INF;
	for (i = 1; i <= Right[0]; ++ i)
		Cap[i + Left[0]][Left[0] + Right[0] + 1] = INF;

	printf("%d\n", ans + maxFlow(0, Left[0] + Right[0] + 1));
	return 0;
}