#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define NMAX 205
#define INF 1000000005

int pred[NMAX],d[NMAX];
int capacitate[NMAX][NMAX];
int flux[NMAX][NMAX],n,m;
int coada[NMAX * NMAX],lungime;
int cost[NMAX][NMAX],sol;
int suma_muchii[NMAX];
int intra[NMAX],iese[NMAX];
int distanta[NMAX][NMAX];

inline int bellman_ford()
{
        int i,j,nod;

        memset(pred,-1,sizeof(pred));
        for(i = 1; i <= 2 * n + 1; i++)
                d[i] = INF;
        d[0] = 0;
        lungime = 1;
        coada[1] = 0;
        for(i = 1; i <= lungime; i++)
        {
                nod = coada[i];
                for(j = 0; j <= 2 * n + 1; j++)
                        if(capacitate[nod][j] > flux[nod][j] && d[nod] + cost[nod][j] < d[j])
                        {
                                d[j] = d[nod] + cost[nod][j];
                                coada[++lungime] = j;
                                pred[j] = nod;
                        }
        }
        return d[2 * n + 1] != INF;
}

int main ()
{
        int i,j,k,a,b,c,val;

        freopen("traseu.in","r",stdin);
        freopen("traseu.out","w",stdout);

        scanf("%d%d",&n,&m);
        for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++)
                        distanta[i][j] = INF;
        int sol2 = 0;
        for(i = 1; i <= m; i++)
        {
                scanf("%d%d%d",&a,&b,&c);
                iese[a]++;
                intra[b]++;
                distanta[a][b] = c;
                sol2 += c;
        }
      // printf("%d\n",sol2);
        for(k = 1; k <= n; k++)
                for(i = 1; i <= n; i++)
                        for(j = 1; j <= n; j++)
                                if(distanta[i][k] + distanta[k][j] < distanta[i][j])
                                        distanta[i][j] = distanta[i][k] + distanta[k][j];
        for(i = 1; i <= n; i++)
                if(intra[i] > iese[i])
                {
                        capacitate[0][i] = intra[i] - iese[i];
                       // printf("Intre 0 si %d punem %d\n",i,capacitate[0][i]);
                }
//123751
        for(i = 1; i <= n; i++)
                if(intra[i] < iese[i])
                {
                        capacitate[n + i][2 * n + 1] = iese[i] - intra[i];
                     //   printf("intre %d si %d punem %d\n",n + i, 2 * n + 1,capacitate[n + i][2 * n + 1]);
                }

        for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++)
                {
                   //     printf("Am pus costul de la %d la %d egal cu %d si cap %d\n",i,j,distanta[i][j],capacitate[0][i]);
                        capacitate[i][j + n] = INF;
                        cost[i][j + n] = distanta[i][j];
                        cost[j + n][i] = -distanta[i][j];
                }

        while(bellman_ford())
        {
                val = INF;
                for(i = 2 * n + 1; i; i = pred[i])
                        val = min(val, capacitate[pred[i]][i] - flux[pred[i]][i]);
                sol += d[2 * n + 1] * val;
             //   printf("%d\n si drumul ",sol);
                for(i = 2 * n + 1; i; i = pred[i])
                {
                 //       printf("%d ",i);
                        flux[pred[i]][i] += val;
                        flux[i][pred[i]] -= val;
                }
               // printf("\n");
        }


        printf("%d\n",sol + sol2);

        return 0;
}