#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];

int eflux(int sursa)
{
        int i, j, tata[NMAX], cup[NMAX], tip[NMAX], lo, hi, min;

        for (i = 0; i < NMAX; i++) Dist[i] = INF, tata[i] = -1, cup[i] = 0, tip[i] = 0;

        Dist[sursa] = 0; Q[0] = sursa; inQ[sursa] = 1; cup[sursa] = -1;

        for (lo = 0, hi = 1; lo <= hi; lo++)
        {
                i = Q[lo];
                if (Gi[i]>Go[i])
                {
                   for (j = 1; j <= N; j++)
                       if ((F[i][j] < Cap[i][j]) && (Dist[j] > Dist[i]+D[i][j]))
                       {
                                Dist[j] = Dist[i]+D[i][j];
                                tata[j] = i;
                                if (!inQ[j]) Q[hi++] = j, inQ[j] = 1;
                       }
                }
                else
                {
                        if ( (cup[i] > 0) && (Dist[j] > Dist[cup[i]]-D[cup[i]][i]) )
                        {
                           Dist[cup[i]] = Dist[i]-D[cup[i]][i];
                           tata[cup[i]] = i; tip[cup[i]] = 1;
                           if (!inQ[cup[i]]) Q[hi++] = cup[i], inQ[cup[i]] = 1;
                        }
                }
        }

        min = INF; j = 0;
        for (i = 1; i <= N; i++)
            if (Gi[i]<Go[i] && min > Dist[i]) min = Dist[i], j = i;

        for (i = j; i > 0; i = tata[i])
            if (tip[i] == 0)
            {
                F[tata[i]][i]++;
                cup[i] = tata[i];
            }
            else F[i][tata[i]]--;
        if (min < INF) { Sol += min; return 1; }
        else return 0;
}

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;

        for (i = 0; i < NMAX; i++)
            for (j = 0; j < NMAX; j++) D[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] = 1;
                Gi[j]++; Go[i]++;
                Sol += c;
        }

        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] = 1;

        j = 1;
        for (i = 1; i <= N && j == 1; i++)
            if (Gi[i]>Go[i]) j = eflux(i);

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

        return 0;
        
}