#include<fstream>
#include<vector>
#include<queue>
#define maxn 65
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;

ifstream in("traseu.in");
ofstream out("traseu.out");

vector<int > vect[maxn];
int N,M,sol,S,D;
int tata[maxn],f[maxn][maxn],In[maxn],Out[maxn],d[maxn],c[maxn][maxn];
bool inqueue[maxn];

int bfs()
{
	queue<int> q;
	int vertex,nod,i;
	for(i=S;i<=D;i++)
	{
		d[i]=INF;
		inqueue[i]=false;
	}
	q.push(S);
	d[S]=0;
	while(!q.empty())
	{
		vertex=q.front();
		q.pop();
		inqueue[vertex]=false;
		for(i=0;i<vect[vertex].size();i++)
		{
			nod=vect[vertex][i];
			if(f[vertex][nod]>0 && d[nod]>d[vertex]+c[vertex][nod])
			{
				d[nod]=d[vertex]+c[vertex][nod];
				tata[nod]=vertex;
				if(inqueue[nod]==false)
				{
					q.push(nod);
					inqueue[nod]=true;
				}
			}
		}
	}
	return d[D]!=INF;
}


void read()
{
	in>>N>>M;
	for(int i=1;i<=M;i++)
	{
		int x,y,z;
		in>>x>>y>>z;
		vect[x].pb(y);
		vect[y].pb(x);
		c[x][y]=z;
		c[y][x]=-z;
		In[y]++;
		Out[x]++;
		f[x][y]=INF;
		sol+=z;
	}
}


int main()
{
	read();
	S=0;
	D=N+1;
	int i;
	for(i=1;i<=N;i++)
	{
		if(In[i]>Out[i])
		{
			f[S][i]=In[i]-Out[i];
			vect[S].pb(i);
			vect[i].pb(S);
		}
		else
			if(Out[i]>In[i])
			{
				f[i][D]=Out[i]-In[i];
				vect[D].pb(i);
				vect[i].pb(D);
			}
	}
	while(bfs())
	{
		int fmin=INF,nod;
		for(nod=D;nod!=S;nod=tata[nod])
			fmin=min(fmin,f[tata[nod]][nod]);
		for(nod=D;nod!=S;nod=tata[nod])
		{
			f[tata[nod]][nod]-=fmin;
			f[nod][tata[nod]]+=fmin;
		}
		sol+=fmin*d[D];
	}
	out<<sol<<"\n";
	return 0;
}