#include <bits/stdc++.h>
#define DIM 210
#define INF 2000000000
using namespace std;

int capacitate[DIM][DIM],flux[DIM][DIM],cst[DIM][DIM],dist[DIM][DIM],dp[DIM];
int g_in[DIM],g_ext[DIM],viz[DIM],t[DIM],f[DIM];
vector <int> L[DIM];
deque <int> c;
int n,m,i,j,k,x,y,cost,sursa,dest;

int bellmanFord (){

    for (int i=sursa;i<=dest;i++){
        dp[i] = INF;
        viz[i] = t[i] = 0;
    }
    c.clear();
    c.push_back(sursa);
    viz[sursa] = 1;
    dp[sursa] = 0;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        viz[nod] = 0;
        for (auto vecin : L[nod]){
            if (capacitate[nod][vecin] > flux[nod][vecin] && dp[nod] + cst[nod][vecin] < dp[vecin]){
                dp[vecin] = dp[nod] + cst[nod][vecin];
                t[vecin] = nod;
                viz[nod] = 1;
                c.push_back(vecin);
            }}}
    return dp[dest] != INF;
}

int main (){

    ifstream cin ("traseu.in");
    ofstream cout ("traseu.out");

    cin>>n>>m;

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            dist[i][j] = cst[i][j] = INF;

    int sol = 0;
    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        g_in[y]++;
        g_ext[x]++;
        dist[x][y] = cost;
        sol += cost;
    }

    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 && dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min (dist[i][j],dist[i][k] + dist[k][j]);

    sursa = 0, dest = n+1;
    for (i=1;i<=n;i++){
        if (g_in[i] > g_ext[i]){
            L[sursa].push_back(i);
            L[i].push_back(sursa);
            capacitate[sursa][i] = g_in[i] - g_ext[i];
            f[i] = 1; /// nodul asta il leg de sursa
            //cout<<sursa<<" "<<i<<" "<<capacitate[sursa][i]<<"\n";
        } else {
            if (g_in[i] < g_ext[i]){
                L[i].push_back(dest);
                L[dest].push_back(i);
                capacitate[i][dest] = g_ext[i] - g_in[i];
                f[i] = 2;
                //cout<<i<<" "<<dest<<" "<<capacitate[i][dest]<<"\n";
            }
        }
    }

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            if (f[i] == 1 && f[j] == 2){
                L[i].push_back(j);
                L[j].push_back(i);
                capacitate[i][j] = INF;
                cst[i][j] = dist[i][j];
                cst[j][i] = -dist[i][j];
                //cout<<i<<" "<<j<<" "<<cst[i][j]<<"\n";
            }
        }

    while (bellmanFord()){
        int x = dest, dif = INF;
        while (x != sursa){
            dif = min (dif,capacitate[t[x]][x] - flux[t[x]][x]);
            x = t[x];
        }


        x = dest;
        while (x != sursa){

            //sol += cst[t[x]][x] * dif;

            flux[t[x]][x] += dif;
            flux[x][t[x]] -= dif;

            x = t[x];
        }

        sol += dif * dp[dest];
    }

    cout<<sol;


    return 0;
}