// Flux maxim de cost minim
// Clasific nodurile in 3 categorii:
// 	A. Nodurile cu gradul de intrare mai mare decat gradul de iesire
// 	B. Nodurile cu gradul de intrare mai mic decat gradul de iesire
// 	C. Nodurile cu gradul de intrare egal cu graul de iesire
// Leg toate nodurile B de destinatie cu capacitatea Gin - Gout
// Leg toate nodurile A de sursa cu capacitatea Gout - Gin
// Fac flux maxim de cost minim, si adun costul acestuia la suma totala initiala

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

#define nmax 65
#define inf 30000

using namespace std;

int n,m,i,j,n1,n2,cost,rez;
int Gin[nmax],Gout[nmax];
int cap[nmax][nmax],fl[nmax][nmax],Cost[nmax][nmax];

int d[nmax],prev[nmax];

int drum() {
	// gasesc un drum de inaintare de la sursa la destinatie
	// returnez 1 daca exista un drum de inaintare
	// returnez 0 daca nu
	
	int i,j,k;

	for(i = 0; i <= n + 1; i++) {
		d[i] = inf;
		prev[i] = -1;
	}
	d[0] = 0;

	for(i = 0; i <= n + 1; i++) 
		for(j = 0; j <= n + 1; j++)
			for(k = 0; k <= n + 1; k++)
				if(d[j] != inf && cap[j][k] > fl[j][k]) {
					int nd = d[j] + Cost[j][k];
					if(nd < d[k]) {
						d[k] = nd;
						prev[k] = j;
					}
				}

	if(d[n + 1] == inf) return 0;
	else {
		int minim = inf;
		int x = n + 1;
		while(x != 0) {
			minim = min(minim,cap[prev[x]][x] - fl[prev[x]][x]);
			x = prev[x];
		}
		x = n + 1;
		while(x != 0) {
			fl[prev[x]][x] += minim;
			fl[x][prev[x]] = -fl[prev[x]][x];
			x = prev[x];
		}
		return 1;
	}
}

int flux() {
	while(drum()) ;
	int r = 0;
	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= n + 1; j++)
			if(fl[i][j] > 0) r += fl[i][j] * Cost[i][j];
	return r;
}

int main() {
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	
	scanf("%d%d",&n,&m);

	rez = 0;
	for(i = 1; i <= m; i++) {
		scanf("%d%d%d",&n1,&n2,&cost);
		rez += cost;
		Gout[n1]++; Gin[n2]++;
		Cost[n1][n2] = cost;
		Cost[n2][n1] = -cost;
		cap[n1][n2] = inf;
	}

	for(i = 1; i <= n; i++) 
		if(Gin[i] < Gout[i]) cap[i][n + 1] = Gout[i] - Gin[i];
		else if(Gout[i] < Gin[i]) cap[0][i] = Gin[i] - Gout[i];

	rez += flux();

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

	return 0;
}