#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 = 1000000000;

int n, m, grIn[N], grOut[N], cost[2 * N][2 * N], s = 0, d = 130, fcost = 0, cap[2 * N][2 * N], flux[2 * N][2 * N], dist[2 * N];
int p[2 * N];
vector<int> v[2 * N];
bool ver[2 * N];

bool bf() {
	queue<int> q;
	int i;
	
	for(i = 0; i < 2 * N; ++i) {
		p[i] = -1;
		ver[i] = 0;
		dist[i] = inf;
	}
	p[s] = 0;
	ver[i] = 1;
	dist[s] = 0;
	q.push(s);
	
	while(!q.empty()) {
		int el = q.front();
		q.pop();
		
		for(vector<int>::iterator it = v[el].begin(); it != v[el].end(); ++it)
			if(cap[el][*it] - flux[el][*it] > 0 && dist[*it] > dist[el] + cost[el][*it]) {
				dist[*it] = dist[el] + cost[el][*it];
				
				p[*it] = el;
				if(!ver[*it]) {
					ver[*it] = 1;
					q.push(*it);
				}
			}
		ver[el] = 0;
	}
	
	if(dist[d] != inf) {
		int vmin = inf;
		
		for(i = d; i != s; i = p[i])
			vmin = min(vmin, cap[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 <= m; ++i) {
		int a, b, c;
		
		in >> a >> b >> c;
		sum += c;
		
		if(cost[a][b + N] == 0)
			cost[a][b + N] = inf, cost[b + N][a] = -inf;
		cost[a][b + N] = min(c, cost[a][b + N]);
		cost[b + N][a] = max(-c, cost[b + n][a]);
		cap[a][b + N] = inf;
		
		v[a].push_back(b + N);
		v[b + N].push_back(a);
		
		grOut[a]++;
		grIn[b]++;
	}
	
	for(i = 1; i <= n; ++i) {
		v[s].push_back(i);
		v[i].push_back(s);
		
		v[i + N].push_back(d);
		v[d].push_back(i + N);
		
		if(grOut[i] > grIn[i])
			cap[i + N][d] = grOut[i] - grIn[i];
		
		if(grOut[i] < grIn[i])
			cap[s][i] = grIn[i] - grOut[i];
	}
	
	out << fmax() + sum;
	
	return 0;
}