#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define nmax 130
#define inf 1<<29

vector <int> g[nmax];
int n, m, d, c[nmax][nmax], dist[nmax][nmax], cost[nmax][nmax], sol, u[nmax], ds[nmax];
int out[nmax], in[nmax], t[nmax];
queue <int> q;

int bellmanford()
{
	int i, nod;
	for (i=1; i<=d; i++) 
	{
		ds[i]=inf;
		u[i]=0;
	}
	q.push(0);
	ds[0]=0;
	u[0]=1;
	while (!q.empty())
	{
		nod=q.front();
		q.pop();
		u[nod]=0;
		for (i=0; i<=d; i++)
			if (c[nod][i]>0)
			{
				if (ds[i]>ds[nod]+cost[nod][i])
				{
					ds[i]=ds[nod]+cost[nod][i];
					t[i]=nod;
					if (!u[i])
					{
						q.push(i);
						u[i]=1;
					}
				}
			}
	}
	return ds[d];
}

void flux()
{
	int fm, nod, x;
	while ((x=bellmanford())!=inf)
	{
		fm=inf;
		nod=d;
		while (nod)
		{
			fm=min(fm, c[t[nod]][nod]);
			nod=t[nod];
		}
		nod=d;
		while (nod)
		{
			c[t[nod]][nod]-=fm;
			c[nod][t[nod]]+=fm;
			nod=t[nod];
		}
		sol+=fm*x;
	}
}

int main()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	scanf("%d %d", &n, &m);
	d=2*n+1;
	int i, x, y, z, j, k;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++) dist[i][j]=inf;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		g[x].push_back (y);
		dist[x][y]=z;
		out[x]++;
		in[y]++;
		sol+=z;
	}
	for (i=1; i<=n; i++) c[0][i]=in[i]-out[i];
	for (i=1; i<=n; i++) c[n+i][d]=out[i]-in[i];
	for (k=1; k<=n; k++)
		for (i=1; i<=n; i++)
			for (j=1; j<=n; j++) 
				dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++) 
			if (i!=j)
			{
				c[i][j+n]=inf;
				cost[i][j+n]=dist[i][j];
				cost[j+n][i]=-dist[i][j];
			}
	flux();
	printf("%d\n",sol);
}