#include <fstream> //9:40
#include <vector>
#include <queue>
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");

#define maxn 64
#define pb push_back
#define mp make_pair
#define oo 200000000
#define ff first
#define ss second

queue <int> Q;
vector <pair<int,int> > A[maxn];
int i,N,M,s,d,R,flmin;
int C[maxn][maxn],gin[maxn],gout[maxn],D[maxn],v[maxn],from[maxn];

inline int min(int a,int b)
{
	return a<b ? a : b;
}

void citire()
{
	int x,y,z;
	fin >> N >> M;
	s=0; d=N+1;
	for(i=1;i<=M;i++)
	{
		fin >> x >> y >> z;
		A[x].pb(mp(y,z));
		A[y].pb(mp(x,-z));
		gout[x]++;
		gin[y]++;
		C[x][y]=oo;
		R+=z;
	}
}

void constr()
{
	for(i=1;i<=N;i++)
	{
		if(gin[i]>gout[i])
		{
			A[s].pb(mp(i,0));
			A[i].pb(mp(s,0));
			C[s][i]=gin[i]-gout[i];
		}
		if(gin[i]<gout[i])
		{
			A[d].pb(mp(i,0));
			A[i].pb(mp(d,0));
			C[i][d]=gout[i]-gin[i];
		}
	}
}

int BF()
{
	int k;
	for(i=1;i<=N+1;i++) { D[i]=oo; v[i]=0; from[i]=0; }
	Q.push(s); v[s]=1; D[s]=0;
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
		for(i=0;i<(int)A[k].size();i++)
			if(C[k][A[k][i].ff]>0 && D[k]+A[k][i].ss<D[A[k][i].ff])
			{
				D[A[k][i].ff]=D[k]+A[k][i].ss;
				from[A[k][i].ff]=k;
				if(!v[A[k][i].ff])
				{
					Q.push(A[k][i].ff);
					v[A[k][i].ff]=1;
				}
			}
		v[k]=0;
	}
	return D[d]<oo;
}

int main()
{
	citire();
	constr();
	while( BF() )
	{
		int k;
		flmin=oo;
		for(k=d;k!=s;k=from[k])
			flmin=min(flmin,C[from[k]][k]);
		for(k=d;k!=s;k=from[k])
		{
			C[from[k]][k]-=flmin;
			C[k][from[k]]+=flmin;
		}
		R+=flmin*D[d];
	}
	fout << R;
}