#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define pb push_back

FILE *in,*out;
queue<int> q;
int v[70],dist[70],d[70][70],cap[70][70],grin[70],grout[70],pred[70];
vector<int> a[70];
int n,cost;
const int inf =1<<29;

int flux ()
{
	int i,nod,minflux;
	for (i=0;i<=n+1;i++)
		dist[i]=inf;
	q.push(0);
	dist[0]=0;	
	v[0]=1;
	while (!q.empty())
	{
		nod=q.front();
		q.pop();
		v[nod]=0;
		for (i=0;i<a[nod].size();i++)
			if (dist[nod]+d[nod][a[nod][i]]<dist[a[nod][i]] && cap[nod][a[nod][i]]>0)
			{
				pred[a[nod][i]]=nod;
				dist[a[nod][i]]=dist[nod]+d[nod][a[nod][i]];
				if (!v[a[nod][i]])
				{
					v[a[nod][i]]=1;
					q.push(a[nod][i]);
				}
			}
	}
	if (dist[n+1]==inf)
		return 0;
	nod=n+1;
	minflux=inf;
	while (nod)
	{
		if (cap[pred[nod]][nod]<minflux)
			minflux=cap[pred[nod]][nod];
		nod=pred[nod];
	}
	nod=n+1;
	while (nod)
	{
		cap[pred[nod]][nod]-=minflux;
		cap[nod][pred[nod]]+=minflux;
		nod=pred[nod];
	}
	cost+=minflux*dist[n+1];
	return minflux;
}
int main()
{
	int x,y,z,i,j,k,m;
	in=fopen("traseu.in","r");
	out=fopen("traseu.out","w");
	fscanf(in,"%d%d",&n,&m);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			d[i][j]=inf;
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d%d",&x,&y,&z);
		grin[y]++;
		grout[x]++;
		d[x][y]=z;
		cost+=z;
	}
	for (k=1;k<=n;k++)
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				if (d[i][k]!=inf && d[k][j]!=inf&& d[i][k]+d[k][j] < d[i][j])
					d[i][j]=d[i][k]+d[k][j];
	for (i=1;i<=n;i++)
			if (grin[i]>grout[i])
			{
					a[0].pb(i);
					a[i].pb(0);
					cap[0][i]=grin[i]-grout[i];
					for (j=1;j<=n;j++)
							if (grin[j]<grout[j])
							{
									a[i].pb(j);
									a[j].pb(i);
									cap[i][j]=inf;
									d[j][i]=-d[i][j];
							}

			}
	for (i=1;i<=n;i++)
			if (grin[i]<grout[i])
			{
					a[i].pb(n+1);
					a[n+1].pb(i);
					cap[i][n+1]=grout[i]-grin[i];
			}

	while (flux())
	{
		//freaca menta
	}
	fprintf(out,"%d\n",cost);
	fclose(in);
	fclose(out);
	return 0;
}