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

template <typename T>
using mat = vector<vector<T>>;

constexpr int inf = 1000000000;

bool bellman_ford(const int surs, const int dest, const mat<int>& muchii,
	const mat<int>& cap, const mat<int>& cost, const mat<int>& flux, vector<int>& dist,
	vector<int>& tata){
	fill(begin(dist), end(dist), inf);
	fill(begin(tata), end(tata), -1);
	
	const int n = muchii.size();

	dist[surs] = 0;

	queue<int> de_viz;
	vector<bool> in_q(n, false);
	de_viz.push(surs);
	in_q[surs] = true;

	while(!de_viz.empty()){
		const int cur = de_viz.front();
		de_viz.pop();
		in_q[cur] = false;

		for(const auto next : muchii[cur]){
			if(cap[cur][next] > flux[cur][next] && dist[next] > dist[cur] + cost[cur][next]){
				dist[next] = dist[cur] + cost[cur][next];
				tata[next] = cur;
				if(!in_q[next]){
					de_viz.emplace(next);
					in_q[next] = true; } } } }
	return tata[dest] != -1; }

int fmcm(const int surs, const int dest, const mat<int>& muchii,
		const mat<int>& cap, const mat<int>& cost, mat<int>& flux){

	const int n = muchii.size();

	vector<int> dist(n, inf), tata(n, -1);
	int rez = 0;

	while(bellman_ford(surs, dest, muchii, cap, cost, flux, dist, tata)){
		int inc = inf;
		for(int nod = dest; nod != surs; nod = tata[nod]){
			inc = min(inc, cap[tata[nod]][nod] - flux[tata[nod]][nod]); }
		for(int nod = dest; nod != surs; nod = tata[nod]){
			flux[tata[nod]][nod] += inc;
			flux[nod][tata[nod]] -= inc; }
		rez += dist[dest] * inc; }
	return rez; }

int main(){
	ifstream f("traseu.in");
	ofstream g("traseu.out");

	int n, m;

	f >> n >> m;

	const int surs = 0, dest = n+1;
	mat<int> muchii(n+2, vector<int>(0, 0)),
		cap(n+2, vector<int>(n+2, 0)),
		cost(n+2, vector<int>(n+2, 0)),
		flux(n+2, vector<int>(n+2, 0));

	auto add_muc = [&](const int a, const int b, const int c, const int d){
		muchii[a].push_back(b);
		muchii[b].push_back(a);
		cap[a][b] = c;
		cap[b][a] = 0;
		cost[a][b] = d;
		cost[b][a] = -d; };

	vector<int> out_deg(n+2, 0), in_deg(n+2, 0);
	int rez = 0;

	for(int i = 0, a, b, c; i < m; ++i){
		f >> a >> b >> c;
		add_muc(a, b, inf, c);
		++out_deg[a];
		++in_deg[b];
		rez += c; }

	for(int i = 1; i <= n; ++i){
		if(in_deg[i] > out_deg[i]){
			add_muc(surs, i, in_deg[i] - out_deg[i], 0); }
		else if(in_deg[i] < out_deg[i]){
			add_muc(i, dest, out_deg[i] - in_deg[i], 0); } }

	
	g << rez + fmcm(surs, dest, muchii, cap, cost, flux);

	return 0; }