#include <stdio.h>
#include <vector>
#define inf 0x7fffffff
#define s (n+1)
#define d (n+2)

using namespace std;

vector<int> graf[65];
vector<int>::iterator u;
int n,m,i,x,y,z,c[65][65],cap[65][65],dplus[65],dminus[65],sol,poz[65],heap[65],aux,minim,difmin[65],dist[65],tt[65],first,f[65][65];
bool k;

inline void heap_up(int p)
{
	while (p>1 && dist[heap[p]]<dist[heap[p>>1]])
	{
		aux=heap[p];
		heap[p]=heap[p>>1];
		heap[p>>1]=aux;
		poz[heap[p]]=p;
		poz[heap[p>>1]]=p>>1;
		p>>=1;
	}
}

inline void heap_down(int p)
{
	while (p*2<=x && dist[heap[p]]>dist[heap[p*2]] || p*2+1<=x && dist[heap[p]]>dist[heap[p*2+1]])
	{
		if (p*2+1<=x)
			if (dist[heap[p*2]]<dist[heap[p*2+1]])
				minim=p*2;
			else
				minim=p*2+1;
		else
			minim=p*2;
		aux=heap[p];
		heap[p]=heap[minim];
		heap[minim]=aux;
		poz[heap[p]]=p;
		poz[heap[minim]]=minim;
		p=minim;
	}
}

int main()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&z);
		graf[x].push_back(y);
		graf[y].push_back(x);
		c[x][y]=z;
		c[y][x]=-z;
		cap[x][y]=inf;
		++dplus[x];
		++dminus[y];
		sol+=z;
	}
	for (i=1;i<=n;++i)
		if (dplus[i]<dminus[i])
		{
			graf[s].push_back(i);
			graf[i].push_back(s);
			cap[s][i]=dminus[i]-dplus[i];
		}
		else
			if (dplus[i]>dminus[i])
			{
				graf[i].push_back(d);
				graf[d].push_back(i);
				cap[i][d]=dplus[i]-dminus[i];
			}
	k=true;
	while (k)
	{
		k=false;
		for (i=1;i<=n+2;++i)
		{
			dist[i]=inf;
			poz[i]=0;
		}
		x=1;
		heap[1]=s;
		poz[s]=1;
		difmin[s]=inf;
		dist[s]=0;
		while (x)
		{
			first=heap[1];
			poz[first]=0;
			if (first==d)
				k=true;
			if (x==1)
				x=0;
			else
			{
				heap[1]=heap[x--];
				heap_down(1);
			}
			for (u=graf[first].begin();u!=graf[first].end();++u)
				if (cap[first][*u]>f[first][*u] && dist[first]+c[first][*u]<dist[*u])
				{
					dist[*u]=dist[first]+c[first][*u];
					if (cap[first][*u]-f[first][*u]<difmin[first])
						difmin[*u]=cap[first][*u]-f[first][*u];
					else
						difmin[*u]=difmin[first];
					tt[*u]=first;
					if (poz[*u])
						heap_up(poz[*u]);
					else
					{
						heap[++x]=*u;
						poz[*u]=x;
						heap_up(x);
					}
				}
		}
		if (k)
			for (i=d;i!=s;i=tt[i])
			{
				f[tt[i]][i]+=difmin[d];
				f[i][tt[i]]-=difmin[d];
				sol+=difmin[d]*c[tt[i]][i];
			}
	}
	printf("%d",sol);
	return 0;
}