#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
using namespace std;
#define FOR(i,a,b) for (i=(a);i<=(b);i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
typedef pair<int,int> ii;
FILE *in,*out;
int pred[70],v[70],n,d[70][70],q[70*70*70],dist[70],cost,grin[70],grout[70];
ii c[70*70];
pair<ii,int> b[70*70];
vector<int> a[70],inv,outv;
const int inf=1<<30;
ii sens(int nr,int x)
{
	if (b[nr].fi.fi==x)
		return mp(b[nr].fi.se,1);
	return mp(b[nr].fi.fi,-1);
}
int ver(int nr, ii next)
{
	if (next.se==1)
	{
		if (c[nr].fi<c[nr].se)
			return 1;
		return 0;
	}
	if (c[nr].fi>0)
		return 1;
	return 0;
}
int ciclu(int nod,int cauta)
{
	if (nod==0)
		return 0;
	if (nod==cauta)
		return 1;
	ii next=sens(pred[nod],nod);
	return ciclu(next.fi,cauta);
}
int diffcap(int x,int y)
{
	if (y==1)
		return c[x].se-c[x].fi;
	else
		return c[x].fi;
}
int flux()
{
	int p,u,i,nod;
	memset(dist,0,sizeof(dist));
	ii next;
	pred[n+1]=0;
	p=1;
	u=1;
	q[1]=0;
	while (p<=u)
	{
		nod=q[p];
		p++;
		v[p]=0;
		FOR(i,0,a[nod].size()-1)
		{
			next=sens(a[nod][i],nod);
			if (ver(a[nod][i],next)&&(dist[next.fi]>dist[nod]+b[a[nod][i]].se*next.se||(dist[next.fi]==0&&next.fi!=0))&&!ciclu(nod,next.fi))
			{
				pred[next.fi]=a[nod][i];
				dist[next.fi]=dist[nod]+b[a[nod][i]].se*next.se;
				if (!v[next.fi])
				{
					v[next.fi]=1;
					u++;
					q[u]=next.fi;
				}
			}
			
		}
	}
	if (pred[n+1]==0)
		return 0;
	i=n+1;
	//printf("Q");
	//scanf("%d",&p);
	int minv=inf;
	while(i)
	{
		next=sens(pred[i],i);
		minv=min(minv,diffcap(pred[i],-next.se));
		i=next.fi;
	//	printf("%d\n",i);
	}
	i=n+1;
	while (i)
	{
		next=sens(pred[i],i);
		c[pred[i]].fi+=minv*(-next.se);
		cost+=minv*(-next.se)*b[pred[i]].se;
		i=next.fi;
	}
//	printf("%d\n",minv);
//	scanf("%d",&minv);
//	fflush(stdout);
	return 1;
}
int main()
{
	in=fopen("traseu.in","r");
	out=fopen("traseu.out","w");
	int m;
	fscanf(in,"%d%d",&n,&m);
	int nr=0,i,j,k,x,y,z;
	FOR(i,1,m)
	{
		fscanf(in,"%d%d%d",&x,&y,&z);
		grin[y]++;
		grout[x]++;
		d[x][y]=z;
		cost+=z;
	}
	FOR(k,1,n)
		FOR(i,1,n)
			FOR(j,1,n)
				if (d[i][k]&&d[k][j]&&(d[i][j]>d[i][k]+d[k][j]||d[i][j]==0)&&i!=j)
					d[i][j]=d[i][k]+d[k][i];
	FOR(i,1,n)
	{
		if (grin[i]==grout[i])
			continue;
		if (grin[i]<grout[i])
			inv.pb(i);
		else
			outv.pb(i);
	}
	FOR(i,0,inv.size()-1)
	{
		nr++;
		b[nr]=mp(mp(0,inv[i]),0);
		c[nr]=mp(0,grin[inv[i]]-grout[inv[i]]);
		a[0].pb(nr);
	}
	FOR(i,0,outv.size()-1)
	{
		nr++;
		b[nr]=mp(mp(outv[i],n+1),0);
		c[nr]=mp(0,grout[outv[i]]-grin[outv[i]]);
		a[outv[i]].pb(nr);
		a[n+1].pb(nr);
	}
	FOR(i,0,inv.size()-1)
		FOR(j,0,outv.size()-1)
		{
			if (d[inv[i]][outv[j]])
			{
				nr++;
				b[nr]=mp(mp(inv[i],outv[j]),d[inv[i]][outv[j]]);
				c[nr]=mp(0,inf);
				a[inv[i]].pb(nr);
				a[outv[j]].pb(nr);
			}
			if (d[j][i])
			{
				nr++;
				b[nr]=mp(mp(outv[j],inv[i]),d[outv[j]][inv[i]]);
				c[nr]=mp(0,inf);
				a[inv[i]].pb(nr);
				a[outv[j]].pb(nr);
			}
		}
	while (flux()) ;
	fprintf(out,"%d\n",cost);
	fclose(in);
	fclose(out);
        return 0;
}