#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

const int kinf = 1000000000, kmax = 1000000000;

int n, verts, edges, ans, roy[65][65], graph[65][65];

void read(){
	assert(freopen("traseu.in", "r", stdin));
	
	scanf("%d%d", &verts, &edges);
	n = verts;
	
	for(int i = 1; i <= edges; ++i){
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		ans += c;
		graph[x][y] = c;
		roy[x][y] = c;
	}
	
	for(int i = 1; i <= verts; ++i)
		for(int j = 1; j <= verts; ++j)
			if(roy[i][j] == 0)
				roy[i][j] = kinf;
}

int cost = 0, f = 0, in[65], ou[65], vis[65], dad[65], cap[65][65], fl[65][65];

void init(){
	for(int i = 1; i <= n + 1; ++i)
		vis[i] = kmax;
	vis[0] = 0;
	dad[0] = -1;
}

int blm(){
	init();

	queue<int> q;
	q.push(0);
	
	while(!q.empty()){
		int now = q.front();
		q.pop();
		
		for(int i = 1; i <= n + 1; ++i)
			if(cap[now][i] > fl[now][i] && vis[i] > vis[now] + roy[now][i]){
				q.push(i);
				vis[i] = vis[now] + roy[now][i];
				dad[i] = now;
			}
	}
	if(vis[n + 1])
		return 1;
	
	return 0;
}

void flow(){
	int cflow;
	while(blm()){
		cflow = kmax;
		
		for(int i = n + 1; i != 0; i = dad[i])
			cflow = min(cflow, cap[dad[i]][i] - fl[dad[i]][i]);
		
		for(int i = n + 1; i != 0; i = dad[i]){
			cost += cflow * roy[dad[i]][i];
			fl[dad[i]][i] += cflow;
			fl[i][dad[i]] -= cflow;
		}
	}
}

void solve(){
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			for(int k = 1; k <= n; ++k)
				roy[j][k] = min(roy[j][k], roy[j][i] + roy[i][k]);
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			if(graph[i][j] < kinf){
				in[j] ++;
				ou[i] ++;
			}
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cap[i][j] = kinf;
	
	for(int i = 1; i <= n; ++i)
		if(ou[i] > in[i])
			cap[0][i] = ou[i] - in[i];
	
	for(int i = 1; i <= n; ++i)
		if(in[i] > ou[i])
			cap[i][n + 1] = in[i] - ou[i];
	
	flow();
	
	ans += cost;
}

void write(){
	assert(freopen("traseu.out", "w", stdout));
	
	printf("%d", ans);
}

int main(){
	read();
	solve();
	write();
	
	return 0;
}