#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n, m, gradint[65], gradext[65], best[70], pred[70];
int S, D, F[70][70], C[70][70], cost[70][70];
vector <int> G[70];
long long sol;
queue <int> Q;

inline void Citire()
{
	int i, x, y, c;
	ifstream fin("traseu.in");
	fin >> n >> m;
	for(i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		gradext[x]++;
		gradint[y]++;
		C[x][y] = 1000000;
		cost[x][y] = c;
		cost[y][x] = -c;
		G[x].push_back(y);
		G[y].push_back(x);
		sol += 1LL * c;
	}
	fin.close();
}

inline void ConstruireRetea()
{
	int i;
	S = n + 1;
	D = n + 2;
	for(i = 1; i <= n; ++i)
	{
		if(gradint[i] < gradext[i])
		{
			C[i][D] = gradext[i] - gradint[i];
			G[i].push_back(D);
			G[D].push_back(i);
			continue;
		}
		if(gradint[i] > gradext[i])
		{
			C[S][i] = gradint[i] - gradext[i];
			G[i].push_back(S);
			G[S].push_back(i);
		}
	}
}

inline bool BellmanFord()
{
	int i, x;
	vector <int>::iterator it;
	for(i = 1; i <= D; ++i)
	{
		best[i] = 1000000000;
		pred[i] = 0;
	}
	best[S] = 0;
	Q.push(S);
	while(!Q.empty())
	{
		x = Q.front();
		Q.pop();
		for(it = G[x].begin(); it != G[x].end(); ++it)
		{
			if(C[x][*it] > F[x][*it] && best[*it] > best[x] + cost[x][*it])
			{
				best[*it] = best[x] + cost[x][*it];
				pred[*it] = x;
				Q.push(*it);
			}
		}
	}
	if(best[D] < 1000000000)
		return true;
	return false;
}

inline void MinCostMaxFlow()
{
	int x, val;
	while(1)
	{
		if(BellmanFord() == false)
			return;
		x = D;
		val = 1000000000;
		while(pred[x])
		{
			val = min(val, C[pred[x]][x] - F[pred[x]][x]);
			x = pred[x];
		}
		x = D;
		while(pred[x])
		{
			F[pred[x]][x] += val;
			F[x][pred[x]] -= val;
			x = pred[x];
		}
		sol += 1LL * val * best[D];
	}
}

inline void Afisare()
{
	ofstream fout("traseu.out");
	fout << sol << "\n";
	fout.close();
}

int main()
{
	Citire();
	ConstruireRetea();
	MinCostMaxFlow();
	Afisare();
	return 0;
}