#include<fstream>
#include<vector>
#include<queue>

#define minim(a,b) ((a)<=(b)?(a):(b))
#define InFile "traseu.in"
#define OutFile "traseu.out"
#define pb push_back
#define mkp make_pair

using namespace std;

ifstream fin (InFile);
ofstream fout (OutFile);

const int MaxN = 64;
const int INF = 0x3f3f3f3f;

int n,m,S,D,ANS;
int C[MaxN][MaxN],d[MaxN],inQ[MaxN],T[MaxN],gri[MaxN],gre[MaxN];
vector< pair<int,int> > G[MaxN];
queue<int> Q;

void Read()
{
	int i,x,y,c;
	fin >> n >> m;
	S = 0 ;
	D = n+1;
	for( i = 0 ; i < m ; i++ )
		{
			fin >> x >> y >> c;
			G[x].pb(mkp(y,c));
			G[y].pb(mkp(x,-c));
			gre[x]++;
			gri[y]++;
			C[x][y] = INF;
			ANS += c;
		}
}

void Build()
{
	int i;
	for( i = 1 ; i <= n ; i++ )
		{
			if( gri[i] > gre[i] )
				{
					G[S].pb(mkp(i,0));
					G[i].pb(mkp(S,0));
					C[S][i] = gri[i] - gre[i];
				}
			if( gri[i] < gre[i] )
				{
					G[D].pb(mkp(i,0));
					G[i].pb(mkp(D,0));
					C[i][D] = gre[i] - gri[i];
				}
		}
}

int Bellman_Ford()
{
	int nod;
	vector< pair<int,int> >::iterator it;
	memset(d,INF,sizeof(d));
	memset(inQ,0,sizeof(inQ));
	memset(T,0,sizeof(T));
	Q.push(S);
	inQ[S] = 1;
	d[S] = 0;
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( d[it->first] > d[nod] + it->second && C[nod][it->first] > 0 )
					{
						d[it->first] = d[nod] + it->second;
						T[it->first] = nod;
						if( !inQ[it->first] )
							{
								Q.push(it->first);
								inQ[it->first] = 1;
							}
					}
			inQ[nod] = 0;
		}
	return d[D] != INF;
}

void Flux()
{
	int fluxmin,nod;
	while( Bellman_Ford() )
		{
			fluxmin = INF;
			for( nod = D ; nod != S ; nod = T[nod] )
				fluxmin = minim(fluxmin , C[T[nod]][nod] );
			for( nod = D ; nod != S ; nod = T[nod] )
				{
					C[T[nod]][nod] -= fluxmin;
					C[nod][T[nod]] += fluxmin;
				}
			ANS += fluxmin*d[D];
		}
}

int main()
{
	Read();
	Build();
	Flux();
	fout << ANS << '\n';
	fin.close();
	fout.close();
	return 0;
}