#include <bits/stdc++.h>

using namespace std;
ifstream fin ("traseu.in");
ofstream fout ("traseu.out");
int n, m, maxflux, cost;
struct much{
    int a, b, c, f, z, per;
};
much ad;
vector <much> a, af;
vector <int> vf[65];
int lene[65][65];
int last[65], d[65], dvechi[65], reald[65], grad[65];

void imi_e_lene_si_vreau_drumuri_scurte(int st){
    for(int i = 1; i <= n; i++){
        lene[st][i] = INT_MAX;
    }
    lene[st][st] = 0;
    for(int j = 1; j < n; j++){
        for(int i = 0; i < m; i++){
            if(lene[st][a[i].a] != INT_MAX){
                lene[st][a[i].b] = min(lene[st][a[i].b], lene[st][a[i].a] + a[i].z);
            }
        }
    }
}

void omul_cu_clopot_vad(){
    for(int i = 0; i <= n + 1; i++){
        reald[i] = INT_MAX;
    }
    reald[0] = 0;
    for(int j = 1; j < n; j++){
        for(int i = 0; i < af.size(); i++){
            if(reald[af[i].a] != INT_MAX){
                reald[af[i].b] = min(reald[af[i].b], reald[af[i].a] + af[i].z);
            }
        }
    }
}

void deschistra(){
    for(int i = 0; i <= n + 1; i++){
        dvechi[i] = reald[i];
        last[i] = -1;
        d[i] = INT_MAX;
    }
    priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    last[0] = -2;
    d[0] = 0;
    reald[0] = 0;
    q.push({0, 0});
    int nod, dnou;
    much nxt;
    while(!q.empty()){
        nod = q.top().second;
        dnou = q.top().first;
        q.pop();
        if(dnou != d[nod]){
            continue;
        }
        for(int i = 0; i < vf[nod].size(); i++){
            nxt = af[vf[nod][i]];
            if(dnou + nxt.z + dvechi[nxt.a] - dvechi[nxt.b] < d[nxt.b] &&
               nxt.f < nxt.c){
                d[nxt.b] = dnou + nxt.z + dvechi[nxt.a] - dvechi[nxt.b];
                reald[nxt.b] = reald[nod] + nxt.z;
                last[nxt.b] = vf[nod][i];
                q.push({d[nxt.b], nxt.b});
            }
        }
    }
}

void fa_un_drum(){
    int nod = n + 1, minim_ude = INT_MAX;
    while(last[nod] != -2){
        minim_ude = min(minim_ude, af[last[nod]].c - af[last[nod]].f);
        nod = af[last[nod]].a;
    }
    maxflux += minim_ude;
    cost += reald[n+1] * minim_ude;
    nod = n + 1;
    while(last[nod] != -2){
        af[last[nod]].f += minim_ude;
        af[af[last[nod]].per].f -= minim_ude;
        nod = af[last[nod]].a;
    }
}

void flux(){
    int lastflux = -1;
    while(lastflux != maxflux){
        lastflux = maxflux;
        deschistra();
        if(last[n+1] != -1){
            fa_un_drum();
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> ad.a >> ad.b >> ad.z;
        cost += ad.z;
        grad[ad.a]++;
        grad[ad.b]--;
        a.push_back(ad);
    }
    for(int i = 1; i <= n; i++){
        imi_e_lene_si_vreau_drumuri_scurte(i);
    }
    for(int i = 1; i <= n; i++){
        if(grad[i] < 0){
            af.push_back({0, i, -grad[i], 0, 0, 0});
            for(int j = 1; j <= n; j++){
                if(grad[j] > 0){
                    af.push_back({i, j, INT_MAX, 0, lene[i][j], 0});
                }
            }
        }
        else if(grad[i] > 0){
            af.push_back({i, n + 1, grad[i], 0, 0, 0});
        }
    }
    int l = af.size();
    for(int i = 0; i < l; i++){
        af.push_back({af[i].b, af[i].a, 0, 0, -af[i].z, i});
        af[i].per = i + l;
        vf[af[i].a].push_back(i);
        vf[af[i].b].push_back(i + l);
    }
    omul_cu_clopot_vad();
    flux();
    fout << cost;
    return 0;
}