#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

ifstream cin("traseu.in");
ofstream cout("traseu.out");

int N, M;
const int nmax = 64, inf = int(1e9);
int dist[nmax][nmax];
int cap[nmax][nmax];
int f[nmax][nmax];
int dgIn[nmax], dgOut[nmax];
int bst[nmax];
int q[nmax*nmax];
bool inQ[nmax];
int T[nmax];
int src, sink;
int ans;

inline void readData() {
	cin>>N>>M;
	int a, b, c;
	for(int i = 0;i < M;i++) {
		cin>>a>>b>>c;
		a--, b--;
		dgOut[a]++;
		dgIn[b]++;
		dist[a][b] = c;
		ans += c;
	}
}

inline void royFloyd() {
	for(int k = 0;k < N;k++) {
		for(int i = 0;i < N;i++) {
			if(dist[i][k] == 0) continue;
			for(int j = 0;j < N;j++) {
				if(i == j || dist[k][j] == 0) continue;
				dist[i][j] = (dist[i][j] == 0 ? dist[i][k] + dist[k][j] : min(dist[i][j],dist[i][k] + dist[k][j]));
			}
		}
	}
}

inline void buildGraph() {
	src = N;
	sink = N + 1;
	for(int i = 0;i < N;i++) {
		if(dgIn[i] > dgOut[i]) {
			cap[src][i] = dgIn[i] - dgOut[i];
		} else
		if(dgIn[i] < dgOut[i]) {
			cap[i][sink] = -dgIn[i] + dgOut[i];
		}

		for(int j = 0;j < N;j++) {
			if(i != j)
			cap[i][j] = inf;
		}
	}
}

inline bool bellman() {
	int L, R;
	L = R = 0;
	for(int i = 0;i < N + 2;i++) {
		bst[i] = inf;
		T[i] = i;
		inQ[i] = false;
	}
	bst[src] = 0;
	q[R++] = src;
	inQ[src] = true;
	while(L < R) {
		int v = q[L++];
		inQ[v] = false;
		for(int w = 0;w < N + 2;w++) {
			if(v != w && f[v][w] < cap[v][w]) {
				if(bst[w] > bst[v] + dist[v][w]) {
					bst[w] = bst[v] + dist[v][w];
					T[w] = v;
					if(inQ[w] == false) {
						inQ[w] = true;
						q[R++] = w;
					}
				}
			}
		}
	}
	return bst[sink] != inf;
}

int maxFlowMinCost() {
	int ret = 0;
	while(bellman()) {
		int fmin = inf;
		for(int v = sink;v != src;v = T[v]) {
			fmin = min(fmin,cap[T[v]][v] - f[T[v]][v]);
		}
		for(int v = sink;v != src;v = T[v]) {
			f[T[v]][v] += fmin;
			f[v][T[v]] -= fmin;
		}
		ret += fmin*bst[sink];
	}
	return ret;
}

int main()
{
	readData();
	royFloyd();
	buildGraph();
	ans += maxFlowMinCost();
	cout<<ans;
	return 0;
}