#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

FILE *f = fopen("traseu.in","r");
FILE *g = fopen("traseu.out","w");

int N,M;
int RoyFloyd[65][65];

int gr[65];
vector<int> G[65];
int C[65][65];
int Cost[65][65];
int F[65][65];
int old_d[65];
int real_d[65];
int d[65];
int T[65];
const int S = 0,D = 64;
int rez = 0;

void addEdge(int x,int y,int cap,int cst){
    C[x][y] = cap;
    Cost[x][y] = cst;
    Cost[y][x] = -cst;
    G[x].push_back(y);
    G[y].push_back(x);
}


bool dijkstra(int S,int D){
    priority_queue < pair <int,int> , vector < pair <int,int> > , greater < pair <int,int> > > H;
    for(int i = S;i <= D;i++){
        d[i] = 1 << 28;
        T[i] = 0;
    }
    d[S] = 0;
    H.push({0,S});
    while(!H.empty()){
        int cost = H.top().first;
        int nod = H.top().second;
        H.pop();
        if(cost != d[nod]){
            continue;
        }
        for(auto it:G[nod]){
            if(F[nod][it] < C[nod][it]){
                int new_d = d[nod] + Cost[nod][it] + old_d[nod] - old_d[it];
                if(new_d < d[it]){
                    d[it] = new_d;
                    real_d[it] = real_d[nod] + Cost[nod][it];
                    T[it] = nod;
                    H.push({d[it],it});
                }
            }
        }
    }
    if(d[D] == 1 << 28){
        return 0;
    }
    memcpy(old_d,real_d,sizeof(real_d));
    int fmin = 1 << 28;
    for(int nod = D;nod != S;nod = T[nod]){
        fmin = min(fmin,C[T[nod]][nod] - F[T[nod]][nod]);
    }
    rez += fmin * real_d[D];
    for(int nod = D;nod != S;nod = T[nod]){
        F[T[nod]][nod] += fmin;
        F[nod][T[nod]] -= fmin;
    }
    return 1;
}

int main(){
    fscanf(f,"%d %d",&N,&M);

    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= N;j++){
            RoyFloyd[i][j] = (i == j ? 0 : 1 << 28);
        }
    }

    for(int i = 1;i <= M;i++){
        int x,y,z;
        fscanf(f,"%d %d %d",&x,&y,&z);
        RoyFloyd[x][y] = z;
        gr[x]--;
        gr[y]++;
        rez += z;
    }

    for(int k = 1;k <= N;k++){
        for(int i = 1;i <= N;i++){
            if(i != k){
                for(int j = 1;j <= N;j++){
                    if(j != k && j != i){
                        RoyFloyd[i][j] = min(RoyFloyd[i][j],RoyFloyd[i][k] + RoyFloyd[k][j]);
                    }
                }
            }
        }
    }

    for(int i = 1;i <= N;i++){
        if(gr[i] < 0){
            addEdge(i,D,-gr[i],0);
        }
        else if(gr[i] > 0){
            addEdge(S,i,gr[i],0);
        }
    }
    for(int i = 1;i <= N;i++){
        if(gr[i] > 0){
            for(int j = 1;j <= N;j++){
                if(gr[j] < 0){
                    addEdge(i,j,1 << 28,RoyFloyd[i][j]);
                }
            }
        }
    }

    while(dijkstra(S,D));

    fprintf(g,"%d",rez);

    fclose(f);
    fclose(g);

    return 0;
}