#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;

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

const int N = 66;
const int inf = 10000000;

int n, m, grad[N], cost[N][N], s = 0, d = 64, fcost = 0, cap[N][N], flux[N][N], dist[N];
int p[N];
bool ver[N];

bool bf() {
	queue<int> q;
	int i;
	
	for(i = 0; i < N; ++i) {
		ver[i] = 0;
		p[i] = 0;
		dist[i] = inf;
	}
	ver[s] = 1;
	dist[s] = 0;
	q.push(s);
	
	while(!q.empty()) {
		int el = q.front();
		q.pop();
		ver[el] = 0;
		
		for(i = s; i <= d; ++i)
			if(cap[el][i] - flux[el][i] > 0 && dist[i] > dist[el] + cost[el][i]) {
				dist[i] = dist[el] + cost[el][i];
				
				p[i] = el;
				
				if(!ver[i]) {
					ver[i] = 1;
					q.push(i);
				}
			}
	}
	
	if(dist[d] != inf) {
		int vmin = inf;
		
		for(i = d; i != s; i = p[i])
			vmin = min(vmin, cap[p[i]][i] - flux[p[i]][i]);
		
		for(i = d; i != s; i = p[i]) {
			flux[p[i]][i] += vmin;
			flux[i][p[i]] -= vmin;
		}
		
		fcost += vmin * dist[d];
		
		return 1;
	}
	return 0;
}

int fmax() {
	
	while(bf());
	
	return fcost;
}

int main() {
	int j, i, sum = 0;
	
	in >> n >> m;
	
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			cost[i][j] = inf;
	for(i = 1; i <= n; ++i)
		cost[i][i] = 0;
	
	for(i = 1; i <= m; ++i) {
		int a, b, c;
		
		in >> a >> b >> c;
		sum += c;
		
		cost[a][b] = c;
		cost[b][a] = -c;
		
		grad[a]++;
		grad[b]--;
	}
	
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(cost[i][j] > 0)
				cap[i][j] = inf;
	
	for(i = 1; i <= n; ++i) {
		
		if(grad[i] > 0)
			cap[i][d] = grad[i];
		
		if(grad[i] < 0)
			cap[s][i] = -grad[i];
	}
	
	out << fmax() + sum;
	
	return 0;
}