#include<fstream>
#include<vector>
#include<deque>
#define INF 1000000000
using namespace std;
int n, m, i, j, k, sol, minim, u, nod;
int d[65], viz[65], gi[65], go[65], t[65];
int a[65][65], c[65][65], f[65][65], z[65][65];
struct muchie{
    int x;
    int y;
    int cost;
};
muchie w[3605];
deque<int> cd;
vector<int> v[65];
ifstream fin("traseu.in");
ofstream fout("traseu.out");
int bf(){
    int i, nod, vecin;
    for(i = 0; i <= n + 1; i++){
        d[i] = INF;
        viz[i] = 0;
        t[i] = 0;
    }
    cd.clear();
    t[0] = -1;
    viz[0] = 1;
    d[0] = 0;
    cd.push_back(0);
    int ok = 0;
    while(!cd.empty()){
        nod = cd.front();
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i];
            if(c[nod][vecin] > f[nod][vecin] && d[vecin] > d[nod] + z[nod][vecin]){
                d[vecin] = d[nod] + z[nod][vecin];
                t[vecin] = nod;
                if(viz[vecin] == 0){
                    viz[vecin] = 1;
                    cd.push_back(vecin);
                }
                if(vecin == n + 1){
                    ok = 1;
                }
            }
        }
        viz[nod] = 0;
        cd.pop_front();
    }
    return ok;
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            z[i][j] = INF;
            a[i][j] = INF;
        }
    }
    for(i = 1; i <= m; i++){
        fin>> w[i].x >> w[i].y >> w[i].cost;
        go[ w[i].x ]++;
        gi[ w[i].y ]++;
        a[ w[i].x ][ w[i].y ] = w[i].cost;
        sol += w[i].cost;
    }
    for(i = 1; i <= n; i++){
        if(gi[i] == go[i]){
            continue;
        }
        if(go[i] < gi[i]){
            c[0][i] = gi[i] - go[i];
            v[0].push_back(i);
            v[i].push_back(0);
        }
        else{
            c[i][n + 1] = go[i] - gi[i];
            v[i].push_back(n + 1);
            v[n + 1].push_back(i);
        }
    }
    for(k = 1; k <= n; k++){
        for(i = 1; i <= n; i++){
            for(j = 1; j <= n; j++){
                if(i != j && i != k && j != k && a[i][j] > a[i][k] + a[k][j]){
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(gi[i] > go[i]){
            for(j = 1; j <= n; j++){
                if(go[j] > gi[j]){
                    c[i][j] = 1000000;
                    z[i][j] = a[i][j];
                    z[j][i] = -a[i][j];
                    v[i].push_back(j);
                    v[j].push_back(i);
                }
            }
        }
    }
    while(bf()){
        minim = 1000000;
        for(u = n + 1; t[u] >= 0; u = t[u]){
            minim = min(minim, c[ t[u] ][u] - f[ t[u] ][u]);
        }
        for(u = n + 1; t[u] >= 0; u = t[u]){
            f[ t[u] ][u] += minim;
            f[u][ t[u] ] -= minim;
        }
        sol += d[n + 1] * minim;
    }
    fout<< sol <<"\n";
    return 0;
}