#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], c [nmax] [nmax], f [nmax] [nmax];
bool viz [nmax];
queue <int> q;
vector <int> g [nmax];
int o [nmax];

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

void cnstr_flux ()
{
	S=n+1;
	D=n+2;
	int i, j;
	for (i=1; i <= n; ++i)
		if (in [i] > out [i])
		{
			g [S].pb (i);
			g [i].pb (0);
			c [S] [i]=in [i]-out [i];
			for (j=1; j <= n; ++j)
				if (out [j] > in [j])
				{
					g [i].pb (j);
					g [j].pb (i);
					c [i] [j]=inf;
					C [j] [i]=-C [i] [j];
				}
		}
	for (i=1; i <= n; ++i)
		if (out [i] > in [i])
		{
			g [i].pb (D);
			g [D].pb (i);
			c [i] [D]=out [i]-in [i];
		}
}

int bellman_ford ()
{
	int i, fr, cst, ind;
	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 (ind=0; ind != g [fr].size (); ++ind) 
		{
			i=g [fr] [ind];
			if (i == fr) continue;
			if (f [fr] [i] == c [fr] [i]) continue;
			cst=C [fr] [i];
			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 (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;
}