#include<stdio.h>
#include<deque>
using namespace std;
deque<int> Q;
long long cost[65][65],cap[65][65],a[65][65],tot,sol,i,j,k,m,n,oo;
void read(),solve(),make_network(),upd();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	oo=2000000000;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=oo;
	for(;m;m--){scanf("%lld%lld%lld",&i,&j,&k);a[i][j]=k;sol+=k;}
}
void solve()
{
	make_network();
	while(tot)upd();
	printf("%lld\n",sol);
}
void make_network()
{
	long long gi[65],ge[65];
	for(i=0;i<=n;i++)gi[i]=ge[i]=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]<oo)
				{ge[i]++;gi[j]++;}
	for(i=1;i<=n;i++)
	{
		if(gi[i]>ge[i])cap[0][i]=gi[i]-ge[i];
		if(gi[i]<ge[i])cap[i][n+1]=ge[i]-gi[i];
	}
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(a[i][j]>a[i][k]+a[k][j])
					a[i][j]=a[i][k]+a[k][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(cap[0][i]&&cap[j][n+1])
			{
				cap[i][j]=n+5;
				cost[i][j]=a[i][j];
				cost[j][i]=-a[i][j];
			}
	for(i=1;i<=n;i++)tot+=cap[0][i];
}
void upd()
{
	long long flow,T[65],x,q[65],dist[65];
	Q.resize(0);T[0]=0;
	for(i=0;i<=n+1;i++){dist[i]=oo;T[i]=i;q[i]=0;};dist[0]=0;
	Q.push_back(0);q[0]=1;
	while(!Q.empty())
	{
		x=Q.front();q[x]=0;
		for(i=0;i<=n+1;i++)
			if(cap[x][i]>0)
				if(dist[i]>dist[x]+cost[x][i])
				{
					if(!q[i])Q.push_back(i);q[i]=1;
					T[i]=x;dist[i]=dist[x]+cost[x][i];
				}
		Q.pop_front();
	}
	flow=tot+1;
	for(i=n+1;i;i=T[i])if(cap[T[i]][i]<flow)flow=cap[T[i]][i];
	tot-=flow;
	for(i=n+1;i;i=T[i]){sol+=flow*cost[T[i]][i];cap[T[i]][i]-=flow;cap[i][T[i]]+=flow;}
}