using namespace std;
#include<fstream>
#include<vector>
#include<queue>
#define pb push_back
#define oo 0x3f3f3f3f
int cst[64][64], capac[64][64];
int d[64], tata[64];
int N,M;
int a[64][64], S, D;
int gi[64], go[64];
queue<int>Q;
int sol;
int viz[64];
vector<int>G[64];
void roy()
{
	int i,j,k;
	for(k = 1; k <= N; ++k)
		for(j = 1; j <= N; ++j)
			for(i = 1; i <= N; ++i)
				if(a[i][k] && a[k][j] && i!=j && (a[i][j] > a[i][k]+a[k][j] || !a[i][j]))
					a[i][j] = a[i][k] + a[k][j];
}
int BFS()
{
	int i,y,x;
	for(i = 0; i <= D; ++i) d[i] = oo, viz[i] = 0;
	for(d[S] = 0, Q.push(S); !Q.empty(); Q.pop())
	{
		x = Q.front();
		viz[x] = 0;
		for(i = 0; i < G[x].size(); ++i)
		{
			y = G[x][i];
			if( capac[x][y] && d[y] > d[x] + cst[x][y] )
			{
				d[y] = d[x] + cst[x][y];
				tata[y] = x;
				if(!viz[y])
				{
					viz[y] = 1;
					Q.push(y);
				}
			}
		}
	}
	if(d[D] == oo) return 0;
	return 1;
}
void flux()
{
	int nod, fx;
	for(;BFS();)
	{
		fx = oo;
		for(nod = D; nod!=S; nod = tata[nod])
			fx = min(fx, capac[tata[nod]][nod]);
		for(nod = D; nod!=S; nod = tata[nod])
		{
			capac[tata[nod]][nod] -= fx;
			capac[nod][tata[nod]] += fx;
		}
		sol += fx * d[D];
	}
}
int main()
{
	ifstream in("traseu.in"); ofstream out("traseu.out");
	in>>N>>M;
	int i,x,y,c,j;
	for(;M;--M)
	{
		in>>x>>y>>c;
		a[x][y] = c;
		gi[y]++; go[x]++;
		sol += c;
	}
	roy();
	S = 0; D = N + 1;
	for(i = 1; i <= N; ++i)
	{
		if(gi[i] > go[i])
		{			
			G[S].pb(i); G[i].pb(S);
			cst[S][i] = 0;
			capac[S][i] = gi[i] - go[i];
		}
		else if(gi[i] < go[i])
		{
			G[i].pb(D); G[D].pb(i);
			capac[i][D] = go[i] - gi[i];
			cst[i][D] = 0;
		}
	}
	for(i = 1; i <= N; ++i)
		if(gi[i] > go[i])
			for(j = 1; j <= N; ++j)
				if(gi[j] < go[j])
				{
					G[i].pb(j); G[j].pb(i);
					cst[i][j] = a[i][j];
					cst[j][i] = -cst[i][j];
					capac[i][j] = oo;;
				}
	flux();
	out<<sol<<"\n";
	return 0;
}