// Traseu
// http://infoarena.ro/problema/traseu

#include <cstdio>
#include <climits>
#include <cstdlib>
#include <queue>
#define MAXN 64
#define INF INT_MAX

using namespace std;

int Adj[MAXN][MAXN], n, m;

int Deg[MAXN], Left[MAXN], Right[MAXN];
int Cost[MAXN][MAXN], Cap[MAXN][MAXN];
int Dist[MAXN], From[MAXN];
bool InQ[MAXN];

void bellmanFord(int src, int snk) {
	queue<int> Q;
	int cur, i;
	
	Dist[src] = 0;
	InQ[src] = true;
	Q.push(src);
	while (Q.empty() == false) {
		cur = Q.front();
		Q.pop();
		InQ[cur] = false;
		
		for (i = 0; i <= snk; ++ i) {
			if (Cap[cur][i] <= 0 || Cost[cur][i] == INF)
				continue;
			if (Dist[i] > Dist[cur] + Cost[cur][i]) {
				Dist[i] = Dist[cur] + Cost[cur][i];
				From[i] = cur;
				if (InQ[i] == false) {
					InQ[i] = true;
					Q.push(i);
				}
			}
		}
		
	}
}

int pathCapacity(int src, int snk) {
	int i;
	for (i = 0; i <= snk; ++ i) {
		Dist[i] = INF;
		From[i] = -1;
		InQ[i] = false;
	}
	bellmanFord(src, snk);
	
	/*for (i = 0; i <= snk; ++ i)
		printf("%d ", Dist[i]);
	printf("\n");
	
	return 0;*/
	int cap = INF;
	for (i = snk; From[i] != -1; i = From[i])
		cap = min(cap, Cap[From[i]][i]);
	
	if (cap == INF)
		return 0;
	
	for (i = snk; From[i] != -1; i = From[i]) {
		Cap[From[i]][i] -= cap;
		Cap[i][From[i]] += cap;
	}
	return cap;
}

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);
	
	#ifdef NDEBUG
		freopen("traseu.out", "w", stdout); 
	#endif
	
	scanf("%d %d", &n, &m);
	
	int i, j; 
	// daca 2 noduri nu sunt conectate, distanta intre ele e INF
	for (i = 1; i <= n; ++ i) {
		// gradele totale sunt initial 0
		Deg[i] = 0;
		for (j = 1; j <= n; ++ j)
			Adj[i][j] = INF;
	}
	
	int eSum = 0;
	for (i = 1; i <= m; ++ i) {
		int v1, v2, c;
		scanf("%d %d %d", &v1, &v2, &c);
		
		Adj[v1][v2] = c;
		Deg[v1] --;
		Deg[v2] ++;
		eSum += c;
	}
	floydWarshall();
	
	Left[0] = Right[0] = 0;
	for (i = 1; i <= n; ++ i) {
		// nodurile cu grade + sunt in dreapta
		// de la ele pleaca "flux"
		if (Deg[i] > 0)
			Left[++ Left[0]] = i;
		if (Deg[i] < 0)
			Right[++ Right[0]] = i;
	}
	// destinatia
	int snk = Left[0] + Right[0] + 1;
	
	// initializez structuri pentru noul graf in care fac cuplaj
	for (i = 0; i <= n + 1; ++ i)
		for (j = 0; j <= n + 1; ++ j) {
			// muchiile nu au capacitati initial
			Cap[i][j] = 0;
			// costurile sunt infinite
			Cost[i][j] = INF;
		}
	for (i = 1; i <= Left[0]; ++ i) {
		Cap[0][i] = abs(Deg[Left[i]]);
		Cost[0][i] = 0;
		Cost[i][0] = 0; // ATENTIE
	}
	for (i = Left[0] + 1; i <= Left[0] + Right[0]; ++ i) {
		Cap[i][snk] = abs(Deg[Right[i - Left[0]]]);
		Cost[i][snk] = 0;
		Cost[snk][i] = 0; // ATENTIE
	}
	for (i = 1; i <= Left[0]; ++ i)
		for (j = Left[0] + 1; j <= Left[0] + Right[0]; ++ j) {
			Cap[i][j] = INF;
			Cost[i][j] = Adj[Left[i]][Right[j - Left[0]]];
			Cost[j][i] = - Adj[Left[i]][Right[j - Left[0]]];
		}
	
	int curCap;
	for (curCap = pathCapacity(0, snk); curCap != 0; curCap = pathCapacity(0, snk))
		eSum += curCap * Dist[snk];
	
	/*printf("%d %d\n", n, Left[0]); 
	for (i = 0; i <= n + 1; ++ i) {
		for (j = 0; j <= n + 1; ++ j)
			printf("%d ", Cost[i][j]);
		printf("\n");
	}*/
	
	printf("%d\n", eSum);
	
	return 0;
}