#include <stdio.h>
#define NMAX 66
#define INF 666000666

int N, M, A[NMAX][NMAX], C[NMAX][NMAX], D[NMAX][NMAX], Dist[NMAX];
int F[NMAX][NMAX], Cap[NMAX][NMAX];
int Q[NMAX*NMAX*NMAX], inQ[NMAX], Gi[NMAX], Go[NMAX];
int T[NMAX], Sol, Cup[NMAX];

#define T N+1

int eflux(int sursa)
{
        int i, j, t[NMAX], min, k, ok;

        for (i = 0; i < NMAX; i++)
            Dist[i] = INF, t[i] = 0;

        Dist[sursa] = 0; t[sursa] = -1;

        for (k = ok = 0; k <= T && !t[T]; k++, ok = 0)
        {
            for (i = 0; i <= T; i++)
               for (j = 0; j <= T; j++)
                   if ( (F[i][j] < 0) && (Dist[j] > Dist[i]-D[i][j]))
                   {
                        Dist[j] = Dist[i]-D[i][j];
                        t[j] = i;
                        ok = 1;
                   }
                   else
                   if ((F[i][j] < Cap[i][j]) && (Dist[j] > Dist[i]+D[i][j]))
                   {
                            Dist[j] = Dist[i]+D[i][j];
                            t[j] = i;
                            ok = 1;
                   }
               if (!ok) break;
        }

        if (Dist[T] == INF) return 0;
        Sol += Dist[T];
        for (i = T; i > 0; i = t[i])
                F[t[i]][i]++, F[i][t[i]]--;
        return 1;
}

int main()
{
        int i, j, c, num = 0, num2 = 0, k;

        freopen("traseu.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (i = 0; i < NMAX; i++)
            for (j = 0; j < NMAX; j++) Cap[i][j] = INF;

        while (M--)
        {
                scanf("%d %d %d", &i, &j, &c);
                A[i][j] = 1; C[i][j] = c; D[i][j] = c; Cap[i][j] = INF;
                Gi[j]++; Go[i]++;
                Sol += c;
        }

        for (i = 1; i <= N; i++)
            if (Gi[i]<Go[i]) A[i][T] = 1, Cap[i][T] = Go[i]-Gi[i], D[i][T] = 0;
            else
                if (Gi[i]>Go[i]) A[0][i] = 1, Cap[0][i] = Gi[i]-Go[i], D[0][i] = 0;

        for (k = 1; k <= N; k++)
            for (i = 1; i <= N; i++)
                for (j = 1; j <= N; j++)
                    if (A[i][k]+A[k][j] == 2)
                       if (D[i][j] > D[i][k]+D[k][j])
                          D[i][j] = D[i][k]+D[k][j], Cap[i][j] = INF;

        j = 1;
        for (i = 1; i <= N && j == 1; i++) j = eflux(0);

        freopen("traseu.out", "w", stdout);
        printf("%d\n", Sol);

        return 0;
        
}