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

#define nmax 65
#define mmax 2*nmax*nmax
#define nod first
#define cost second
#define pb push_back
#define inf INT_MAX/2

using namespace std;

typedef pair <int, int> ii;

int S, D, R, n, m, pred [nmax], C [nmax] [nmax], in [nmax], out [nmax], w [nmax], c [nmax] [nmax], f [nmax] [nmax];
bool viz [nmax];
queue <int> q;
int o [nmax];

inline int max (int a, int b)
{
	return (a>b)? a:b;
}

void cnstr_flux ()
{
	S=w [0]+1;
	D=w [0]+2;
	int i, j;
	for (i=1; i <= w [0]; ++i)
	{
		c [i] [D]=max (out [w [i]]-in [w [i]], 0);
		c [S] [i]=max (in [w [i]]-out [w [i]], 0);
		for (j=1; j <= w [0]; ++j)
			if (i != j)
				c [i] [j]=inf;	
	}
}

int bellman_ford ()
{
	int i, fr, cst;
	for (i=1; i <= D; ++i)
		o [i]=inf;
	q.push (S);
	o [S]=0;
	viz [S]=true;
	while (!q.empty ())
	{
		fr=q.front ();
		viz [fr]=false;
		q.pop ();	
		for (i=1; i <= D; ++i) 
		{
			if (i == fr) continue;
			if (f [fr] [i] == c [fr] [i]) continue;
			cst=C [w [fr]] [w [i]];
			if (fr > w [0] || i > w [0]) cst=0;
			if (o [i] <= o [fr] + cst) continue;
			o [i]=o [fr]+cst;
			pred [i]=fr;
			if (viz [i] == true) continue;
			viz [i]=true;
			q.push (i);
		}				
	}
	if (o [D] == inf) return -1;
	return o [D];
}

int flux ()
{
	int i, flow, x, R=0;
	while (1)
	{
		x=bellman_ford ();
		if (x == -1) return R;
		flow=inf;
		for (i=D; i != S; i=pred [i])
			if (flow > c [pred [i]] [i]-f [pred [i]] [i])
				flow=c [pred [i]] [i]-f [pred [i]] [i];
		for (i=D; i != S; i=pred [i])
		{
			f [pred [i]] [i] += flow;
			f [i] [pred [i]] -= flow;
		}
		R += x*flow;
	}
}

int main ()
{
	freopen ("traseu.in", "r", stdin);
	freopen ("traseu.out", "w", stdout);
	int i, j, k, a, b, c;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= n; ++i)
		for (j=1; j <= n; ++j)
			C [i] [j]=inf;
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d%d", &a, &b, &c);
		C [a] [b]=c;
		R += c;
		++in [b];
		++out [a];
	}
	for (i=1; i <= n; ++i)
		if (in [i] != out [i])
			w [++w [0]]=i;
	for (k=1; k <= n; ++k)
		for (i=1; i <= n; ++i)
			for (j=1; j <= n; ++j)
				if (i != j && C [i] [k]+C [k] [j] < C [i] [j])	
					C [i] [j]=C [i] [k]+C [k] [j];
	cnstr_flux ();
	printf ("%d\n", R+flux ());
	return 0;
}