# include <stdio.h>

# define  _fin  "traseu.in"
# define  _fout "traseu.out"

# define  maxn  70
# define  maxm  3000

# define  inf   1000000027


int m, n, v[maxn][maxn], vc[maxn][maxn];	// cost
int dg[maxn];								// grad iesire - grad intrare

int cap[maxn][maxn], f[maxn][maxn];
int d[maxn], prec[maxn], cost;
int s, t, sol;


void readf()
{
	freopen(_fin, "r", stdin);
	int i, x, y, c, j;
	
	for (i=1; i<maxn; i++) for (j=1; j<maxn; j++) vc[i][j] = inf;
	for (i=1; i<maxn; i++) vc[i][i] = 0;
	
	for (scanf("%d%d", &n, &m), i=1; i<=m; i++)
		scanf("%d %d %d", &x, &y, &c), sol += c,
		vc[x][y] = c, v[x][y] = 1, dg[x]++, dg[y]--;
}

inline int min(int a, int b) { return a<b?a:b; }

void presolve()
{
	int i, j, k;
	
	for (k=1; k<=n; k++)
		for (i=1; i<=n; i++)
			for (j=1; j<=n; j++)
				vc[i][j] = min( vc[i][j], vc[i][k] + vc[k][j] );
	
	// create flow network
	s=n+1, t=n+2;
	
	for (i=1; i<=n; i++)
		if ( dg[i] < 0 )				// grad iesire < grad intrare
			v[s][i]=2, vc[s][i]=0,
			cap[s][i]=-dg[i],
            v[i][s]=2, vc[i][s]=0,		// NEW
            cap[i][s]=0;				// NEW
		else if ( dg[i] > 0 )
			v[i][t]=2, vc[i][t]=0,
			cap[i][t]=dg[i],
			v[t][i]=2, vc[t][i]=0,		// NEW
			cap[t][i]=0;				// NEW
	
	for (i=1; i<=n; i++)
		if ( v[s][i] )
			for (j=1; j<=n; j++)
				if ( v[j][t] )
					v[i][j] = 2, cap[i][j] = inf,
                    v[j][i] = 2, cap[j][i] = 0, vc[j][i] = -vc[i][j];
}

int bellmanFord()
{
	int i, j, step, relax=1, w;
	
	for (i=1; i<maxn; i++) d[i] = inf, prec[i]=-1;
	d[s] = prec[s] = 0;
	
	for (step=1; step<n+2 && relax; step++)
	{
		relax = 0;
	
		for (i=1; i<=n+2; i++)
			for (j=1; j<=n+2; j++)
				if ( v[i][j]==2 && cap[i][j]-f[i][j] > 0 )
					if ( d[j] > d[i] + vc[i][j] )
						d[j] = d[i] + vc[i][j],
						prec[j] = i, relax=1;
	}
	
	if ( prec[t] == -1 ) return 0;	// done
	
	for (w=t; prec[w]; w=prec[w])
		++f[ prec[w] ][ w ],
		--f[ w ][ prec[w] ];
	
	cost = d[t];
	
	return 1;
}

void solve()
{
	presolve();
	
	while ( bellmanFord() )
		sol += cost;
/*    int i, j;
    
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if ( v[i][j]==2 )
               sol += vc[i][j] * f[i][j];  */
}

void writef()
{
	freopen(_fout, "w", stdout);
	printf("%d\n", sol);
}

int main()
{
	readf();
	solve();
	writef();
	
	return 0;
}