#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#define NMAX 65
#define INF 1000000000
#define pb push_back
using namespace std;
int n,m,A[NMAX][NMAX],in[NMAX],out[NMAX],B[NMAX],rez,C[NMAX][NMAX],F[NMAX][NMAX];
int sursa,dest,dad[NMAX],dist[NMAX];
vector <int> D[NMAX];
queue <int> Q;
char ok,marc[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y,z;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		A[x][y]=z;
		out[x]++; in[y]++;
		rez+=z;
	}
}
void roy_floyd()
{
	int i,j,k;
	for (k=1; k<=n; k++)
		for (i=1; i<=n; i++)
			for (j=1; j<=n; j++)
				if (i!=j && A[i][k] && A[k][j])
					if (!A[i][j] || A[i][j]>A[i][k]+A[k][j])
						A[i][j]=A[i][k]+A[k][j];
}
void make_graph()
{
	int i,j;
	for (i=1; i<=n; i++)
		if (out[i]<in[i])
			for (j=1; j<=n; j++)
				if (in[j]<out[j] && A[i][j]>0)
				{
					D[i].pb(j); D[j].pb(i);
					A[j][i]=-A[i][j];
					C[i][j]=INF;
				}
	for (i=1; i<=n; i++)
	{
		if (out[i]<in[i])
		{
			D[0].pb(i),D[i].pb(0);
			C[0][i]=in[i]-out[i];
		}
		if (in[i]<out[i])
		{
			D[i].pb(n+1),D[n+1].pb(i);
			C[i][n+1]=out[i]-in[i];
		}
	}
	sursa=0; dest=n+1;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
int bford()
{
	int i,nod,vec;
	for (i=1; i<=n; i++)
		dist[i]=INF;
	dist[dest]=INF;
	Q.push(sursa); marc[sursa]=1;
	while (!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		marc[nod]=0;
		for (i=0; i<D[nod].size(); i++)
		{
			vec=D[nod][i];
			if (C[nod][vec]-F[nod][vec]>0 && dist[vec]>dist[nod]+A[nod][vec])
			{
				dist[vec]=dist[nod]+A[nod][vec];
				dad[vec]=nod;
				if (!marc[vec])
					Q.push(vec),marc[vec]=1;
			}
		}
	}
	if (dist[dest]!=INF)
	{
		ok=1;
		int val=INF;
		for (i=dest; i!=sursa; i=dad[i])
			val=min(val,C[dad[i]][i]-F[dad[i]][i]);
		for (i=dest; i!=sursa; i=dad[i])
		{
			F[dad[i]][i]+=val;
			F[i][dad[i]]-=val;
		}
		return val*dist[dest];
	}
	return 0;
}
void solve()
{
	make_graph();
	ok=1;
	while (ok)
	{
		ok=0;
		rez+=bford();
	}
}
int main()
{
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
	read();
	roy_floyd();
	solve();
	printf("%d\n",rez);
	return 0;
}