# include <stdio.h>
# define _fin "traseu.in"
# define _fout "traseu.out"
# define maxn 62
# 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 (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]; // costul
else if ( dg[i] > 0 )
v[i][t]=2, vc[i][t]=0,
cap[i][t]=dg[i];
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;
}
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;
}
void writef()
{
freopen(_fout, "w", stdout);
printf("%d\n", sol);
}
int main()
{
readf();
solve();
writef();
return 0;
}