// incercam sa transformam graful in unul "eulerian", adica introducem un nod fictiv
// din fiecare nod din care mai trebuie sa iasa muchii ducem atatea muchii catre nodul fictiv
// si de la nodul fictiv atatea muchii catre fiecare nod in care trebuie sa intre muchii.
// acum graful este eulerian.
// de fapt procedam astfel: in loc de un nod fictiv punem doua
// sursa, din care ducem muchii de capacitate c catre fiecare nod din care trebuie sa mai plece
// muchii (unde c este numarul de muchii care trebuie sa plece din el)
// destinatia, spre care punem muchii din fiecare nod din care tre sa iasa muchii (de capacitate
// numarul de muchii care trebuie sa iasa.) costul acestor muchii este 0.
// de la muchiile legate de sursa la cele legate de destinatie punem cate o muchie cu
// capacitate infinit si cost egal cu distanta minima dintre cele doua noduri.
// facem flux maxim de cost minim. la fiecare drum de crestere adunam la solutie produsul
// dintre lungimea costul drumului si fluxul adunat. fiecare drum de crestere este traseu
// parcurs prin muchiile adaugate. sa adauga la solutie si suma costurilor muchiilor.

#include <fstream>
#include <iostream>
#include <deque>
#include <bitset>
#include <vector>
#define DIM 62
#define INF 100000000

using namespace std;

int c[DIM][DIM], f[DIM][DIM], z[DIM][DIM], a[DIM][DIM];
vector<int> L[DIM];
int v[DIM], d[DIM], t[DIM];
bitset<DIM> iq;
deque<int> q;

int n, m, sol, x, y, cost, minim, u;

int bf() {
    int findDest = 0;
    iq.reset();
    q.clear();

    q.push_back(0);
    iq[0] = 1;
    v[0] = 0;
    for (int i=1;i<=n+1;i++){
        v[i] = INF;
        t[i] = 0;
    }
    while (!q.empty()) {
        int nod = q.front();
        q.pop_front();
        iq[nod] = 0;
        for (int i=0;i<L[nod].size();i++) {
            int vecin = L[nod][i];
            if (c[nod][vecin] > f[nod][vecin] && v[vecin] > v[nod] + z[nod][vecin]) {
                v[vecin] = v[nod] + z[nod][vecin];
                if (!iq[vecin]) {
                    iq[vecin] = 1;
                    q.push_back(vecin);
                }
                if (vecin == n+1) {
                    findDest = 1;
                    //return 1;
                }
                t[vecin] = nod;
            }
        }
    }
    return findDest;
}

int main() {
    ifstream fin ("traseu.in");
    ofstream fout("traseu.out");

    fin>>n>>m;

    for (int i=1;i<=n;i++)
        for (int j = 1; j<=n; j++)
            a[i][j] = INF;

    for (int i=1;i<=m;i++) {
        fin>>x>>y>>cost;
        a[x][y] = cost;
        d[x]++;
        d[y]--;
        sol += cost;
    }

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i != j)
                for (int k = 1; k<=n; k++)
                    if (i!=k && k!=j && a[i][j] > a[i][k] + a[k][j])
                        a[i][j] = a[i][k] + a[k][j];

    for (int i=1;i<=n;i++) {
        if (d[i] < 0) {
            // pun muchie intre sursa (0) si i
            c[0][i] = -d[i];
            L[0].push_back(i);
            L[i].push_back(0);
        }
        if (d[i] > 0) {
            c[i][n+1] = d[i];
            L[i].push_back(n+1);
            L[n+1].push_back(i);
        }
    }

    for (int i=1;i<=n; i++)
        for (int j=1;j<=n;j++)
            if (d[i] < 0 && d[j] > 0 && a[i][j] != INF) {
                c[i][j] = INF;
                z[i][j] = a[i][j];
                z[j][i] = -a[i][j];
                L[i].push_back(j);
                L[j].push_back(i);
            }

    while(bf()) {
        minim = INF;
        u = n+1;
        while (u!=0) {
            minim = min(minim, c[ t[u] ][u] - f[ t[u] ][u]);
            u = t[u];
        }
        /*
        if (minim == 0 || minim == INF)
            cout<<"NOK";
        cout<<minim<<"\n";
        */
        u = n+1;
        while (u!=0) {
            f[ t[u] ][u] += minim;
            f[ u ][t[u]] -= minim;
            sol += z[ t[u] ][u] * minim;
            u = t[u];
        }
    }

    fout<<sol;
    return 0;
}