#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("traseu.in");
ofstream g("traseu.out");

#define nmax 62
#define ll long long
#define inf (1<<30)
#define nrDemuchii nmax*nmax

int n, m, CostTotal, iese[nmax], intra[nmax], cost[nmax][nmax], Dist[nmax][nmax], dist[nmax], t[nmax];
bool inCoada[nmax], viz[nmax];
vector< pair<int,int> > gf[nmax];
vector<int> g2[nmax];
int flux[nmax][nmax], capac[nmax][nmax];
int q[nmax*nrDemuchii];
void citeste(){
    f >> n >> m;
    int x, y, z;
    for(int i=1; i<=m; ++i){
        f >> x >> y >> z;
        gf[x].push_back( make_pair(y, z) );
        ++iese[x]; ++intra[y];
        CostTotal += z;
    }
}

void distanta(int nod){
    for(int i=0; i<nmax; ++i) dist[i] = inf, inCoada[i] = 0;
    int st=1; int dr = 0;
    q[++dr] = nod; inCoada[nod] = 1; dist[nod] = 0;
    for(; st<=dr; ){
        int nod = q[st]; ++st;
        inCoada[nod] = 0;
        for(int i=0; i<gf[nod].size(); ++i){
            int vc = gf[nod][i].first;
            int cost = gf[nod][i].second;
            if (dist[vc] > dist[nod] + cost){
                dist[vc] = dist[nod] + cost;
                if (inCoada[vc] == 0){
                    inCoada[vc] = 1;
                    q[++dr] = vc;
                }
            }
        }
    }
}

void bagaDistante(){
    for(int i=1; i<=n; ++i){
        distanta(i);
        for(int j=1; j<=n; ++j){
            Dist[i][j] = dist[j];
            //cout << i << "  " << j << " " << dist[j] << "\n";
        }
    }
}

void leagaS(int S, int i){
    g2[S].push_back(i);
    g2[i].push_back(S);
    capac[S][i] = intra[i]-iese[i];// tot timpul intra[i] > iese[i]
    cost[S][i] = 0;
}

void leagaD(int D, int i){
    g2[D].push_back(i);
    g2[i].push_back(D);
    capac[i][D] = iese[i] - intra[i];
    cost[i][D] = 0;
}

void faGraf(){
    for(int i=1; i<=n; ++i){
        if (intra[i] > iese[i]){// ii in partea stanga
            for(int j=1; j<=n; ++j){
                if (intra[j] < iese[j]){// ii in dreapta
                    if (Dist[i][j] == inf) continue;// nu exista drum intre cele 2 nodujri
                    g2[i].push_back(j);
                    g2[j].push_back(i);
                    capac[i][j] = inf;
                    cost[i][j] = Dist[i][j];
                }
            }
        }
    }
}

int Bf(int S, int D){
    for(int i=0; i<nmax; ++i) viz[i] = 0, t[i] = 0, dist[i] = inf;
    dist[S] = 0;
    int st = 1; int dr = 0;
    q[++dr] = S; viz[S] = 1;
    for(; st<=dr; ){
        int nod = q[st]; ++st;
        viz[nod] = 0;
        for(int i=0; i<g2[nod].size(); ++i){
            int vc = g2[nod][i];
            if ( flux[nod][vc] < capac[nod][vc] && dist[vc] > dist[nod] + cost[nod][vc] ){
                dist[vc] = dist[nod] + cost[nod][vc];
                t[vc] = nod;
                if (viz[vc] == 0){
                    viz[vc] = 1;
                    q[++dr] = vc;
                }
            }
        }
    }

    return dist[D];
}

void rezolva(){
    // deci facand abstractie de costurile de pe muchii eu pot face un ciclu in graf daca fiecare nod are gradul intrare = cu gradul de iesire
    // daca apare cazul asta initial atunci clar raspunsul va fi suma costurilor fiecarei muchii
    // dar evident poate as nu fie asa; asa ca o sa trebuiasca sa mai bag niste muchii a. i. graful sa admita un ciclu euler
    // doar ca ideea ar fi ca eu doar o sa refolosesc niste muchii nu o sa adaug altele noi pt ca daca le-as adauga ciclul s-ar transforma in lanturi
    // asa ca impart graful in 2 multimi : in partea stanga o sa am nodurile cu gradul de iesire mai < decat ala de intrare
    // pt ca eu acum daca un nod e in partea stanga insemana ca o sa mai refolosesc o muchie de atatea ori pana cand ajugne sa fie == cu gradul de intrare
    // si la fel in partea dreapta pun nodurile cu gradul de iesire mai mare decat ala de intrare; in astea o sa intre muchii si o sa le egaleze pe ala de isire
    // si apoi o sa imi bag o sursa si o destinatie; sursa o sa leg de fiecare nod din partea stanga avand capacitatea == cu difereta dintre grade si cost 0
    // la fel peentru destinatie
    // apoi intre 2 noduri (diferite de sursa si destinatie) o sa bag o muchie de la x la y cu costul egal cu distanta minima dintre x si y si capacitate infinita
    // bag capacitate infinita pentru ca acele noduri care ar fi pe drumul de la x la y si-ar anula nr de muchii care intre cu alea care ies
    // si fluxul imi e delimitat de capacitatea baga intre sursa si fiecare nod din multimea stanga la fel pt alea din partea dreapta si destinatie
    for(int i=1; i<=n; ++i){
        if (intra[i] > iese[i]){// e in partea stanga
            leagaS(0, i);// leg sursa de nodul i
        }else if (intra[i] < iese[i]){
            leagaD(n+1, i);
        }
    }

    bagaDistante();// imi fac distanta minima de la i la j in Dist[i][j];
    faGraf();// imi construiesc graful al 2 lea

    // si acum bag un flux maxim de cost minim
    int S = 0; int D = n+1;
    for(int ok=1; ok!=0; ){
        int Cost = Bf(S, D);
        if (Cost == inf){
            break;
        }
        int Min = inf;
        for(int i=D; i!=S; i=t[i]){
            // am muchia t[i] - > i
            Min = min(Min, capac[ t[i] ][i] - flux[ t[i] ][i]);
        }
        // bag fluxul
        for(int i=D; i!=S; i=t[i]){
            flux[ t[i] ][i] += Min;
            flux[i][ t[i] ] -= Min;
        }
        CostTotal += (Min * Cost);// adica o sa folosesc muchiile alaea de pe drum de Min ori
    }
    cout <<  CostTotal << "\n";
    g <<  CostTotal << "\n";
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}