#include <stdio.h>
#include <string.h>

#define T N+1

#define NMAX 2*69
#define INF 666000666

int N, M, C[NMAX][NMAX], D[NMAX][NMAX], Dist[NMAX];
int F[NMAX][NMAX], Cap[NMAX][NMAX], Sol, t[NMAX];
int Gi[NMAX], Go[NMAX], X[NMAX];

int flow;

int eflux(int sursa)
{
        int i, j, k, minf, 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; k++, ok = 0)
        {
            for (i = 0; i <= T; i++)
               for (j = 0; j <= T; j++)
                      if (F[i][j] < 0)
                      {
                         if (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])
                          if (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;
        flow++;
        for (i = T, minf = INF; i > 0; i = t[i])
            if (minf > Cap[t[i]][i]-F[t[i]][i])
                minf = Cap[t[i]][i]-F[t[i]][i];
        for (i = T; i > 0; i = t[i])
                F[t[i]][i]+=minf, F[i][t[i]]-=minf;
        return 1;
}

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

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

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

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

        for (i = 1; i <= N; i++)
            if (Gi[i]<Go[i]) Cap[i][T] = Go[i]-Gi[i], D[i][T] = 0;
            else
                if (Gi[i]>Go[i]) 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 (D[i][j] > D[i][k]+D[k][j]) D[i][j] = D[i][k]+D[k][j];

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++)
                if (Gi[i]>Go[i] && Gi[j]<Go[j])
                {
                        Cap[i][j] = INF; Cap[j][i] = 0;
                        D[j][i] = -D[i][j];
                }
                
        j = 1;
        for (i = 1; i <= N && j == 1; i++) j = eflux(0);

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++)
                if (F[i][j]>0)
                   Sol += (F[i][j]*D[i][j]);

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

        return 0;
        
}