#include <stdio.h>
#define maxn 100
#define INF 10000001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)
 
int N, M;
int gi[maxn], ge[maxn], t[maxn], s[maxn], d[maxn];
int a[maxn][maxn], f[maxn][maxn], c[maxn][maxn], m[maxn][maxn];
FILE *fin = fopen("traseu.in", "rt"), *fout = fopen("traseu.out", "wt");
 
int bellman()
{
    int nr, i, j, k, ok;
    FOR(i, 0, N+1) d[i] = INF;
    d[0] = 0;
    for (ok = nr = 1; nr < N && ok; nr++)
        for (ok = i = 0; i <= N + 1; i++)
            for(j = 0; j <= N + 1; j++)
                if (i != j && m[i][j])
                {
                    if (c[i][j] > f[i][j] && d[j] > d[i] + a[i][j])
                    {
                        d[j] = d[i] + a[i][j];
                        t[j] = i;
                        ok = 1;
                    }
                    if (c[j][i] > f[j][i] && d[i] > d[j] - a[i][j])
                    {
                        d[i] = d[j] - a[i][j];
                        t[i] = j;
                        ok = 1;
                    }
                }
 
    return d[N+1] != INF;
 
}
 
int main()
{
    int x, y, ct, i, j, k, tcost = 0;
    fscanf(fin, "%d %d", &N, &M);
    FOR(i, 1, M)
    {
        fscanf(fin, "%d %d %d", &x, &y, &ct);
        a[x][y] = ct;
        c[x][y] = INF;
        m[x][y] = 1;
        ge[x]++, gi[y]++;
        tcost += ct;
    }
    FOR(i, 0, N+1) FOR(j, 0, N+1)
        if (!a[i][j]) a[i][j] = INF;
     
    FOR(k, 1, N)
        FOR(i, 1, N)
            FOR(j, 1, N)
                if (i != j && a[i][j] > a[i][k] + a[k][j])
                    a[i][j] = a[i][k] + a[k][j];
     
    FOR(i, 1, N)
    {
        if (gi[i] > ge[i]) c[0][i] = gi[i] - ge[i], a[0][i] = 0, m[0][i] = 1;
        if (ge[i] > gi[i]) c[i][N+1] = ge[i] - gi[i], a[i][N+1] = 0, m[i][N+1] = 1;
    }
 
    int flux = 0, r;
 
    for (flux = 0; bellman(); flux += r, tcost += r*d[N+1])
    {
        r = INF;
        for(i = N+1; i != 0; i = t[i])
            if (r > c[t[i]][i] - f[t[i]][i])
                r = c[t[i]][i] - f[t[i]][i];
        for (i = N+1; i != 0; i = t[i])
            f[t[i]][i] += r,
            f[i][t[i]] -= r;
    }
    fprintf(fout, "%d\n", tcost);
    fclose(fin), fclose(fout);
    return 0;
}