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

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

        for(i = 1; i <= n; i++)
                if(intra[i] < iese[i])
                        capacitate[n + i][2 * n + 1] = iese[i] - intra[i];
 
        for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++)
                {
                        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;
                for(i = 2 * n + 1; i; i = pred[i])
                {
                        flux[pred[i]][i] += val;
                        flux[i][pred[i]] -= val;
                }
        }
 
 
        printf("%d\n",sol + sol2);
 
        return 0;
}