#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
// #include <bits/std++.h>
#define in  fin
#define out fout

using namespace std;
const int NMAX = 60 + 60 + 5;
using ll = long long;

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

// broo a fost foarte fain azi
// gen am luat pauza de la rockstadt ca na
// si am fost in drumetie
// ma rog de dimineata am fost la un sanctuar de ursi
// si o fost tare cute
// si dupa la canionul cu 7 trepte or something
// dar peak!!

struct muchie{
    int x, y, pereche, c, f, cost;
};

vector<muchie> mch;
vector<int> g[NMAX];
vector< pair<int, int> > cryptopsy[NMAX];
pair<int, int> last[NMAX];
int the_real_ones[NMAX], unchii[NMAX], perchance[NMAX];
bool mrc[NMAX];
int n;
int sursie, noelle;
int cezar[61][61];

void add_muchie(int x, int y, int c, int cost){
    int id = mch.size(), idp = mch.size() + 1;

    mch.push_back({x, y, idp, c, 0,  cost});
    mch.push_back({y, x, id,  0, 0, -cost});

    g[x].push_back(id);
    g[y].push_back(idp);
}

void clopot_barbat_vad(){
    for(int i = 1; i <= n; i++){
        unchii[i] = INT_MAX;
    }

    queue<int> q;
    q.push(sursie);
    unchii[sursie] = 0;
    mrc[sursie] = 1;

    while(!q.empty()){
        int x = q.front(); q.pop();
        for(const int &id : g[x]){
            int y = mch[id].y;
            if(unchii[y] > unchii[x] + mch[id].cost){
                // vlad de ce verifici capacitatea in bellman ford nu e nevoie
                unchii[y] = unchii[x] + mch[id].cost;
                if(!mrc[y]){
                    q.push(y);
                    mrc[y] = 1;
                }
            }
        }
        mrc[x] = 0;
    }
}

int flux, cost; // nu is original ok
// ma dor genunchii
// :C
bool deschistra(){
    for(int i = 1; i <= 2 * n + 2; i++){
        perchance[i] = INT_MAX;
        last[i] = {0, -1};
    }

    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
    perchance[sursie] = 0;
    the_real_ones[sursie] = 0;
    pq.push({0, sursie});
    
    while(!pq.empty()){
        int x = pq.top().second, d = pq.top().first;
        pq.pop();

        if(d != perchance[x]) continue;

        for(const int &id : g[x]){
            int y = mch[id].y;
            if(mch[id].c == mch[id].f) continue;

            int im_a_new_soul = perchance[x] + mch[id].cost + unchii[x] - unchii[y];
            if(im_a_new_soul < perchance[y]){
                perchance[y] = im_a_new_soul;
                the_real_ones[y] = the_real_ones[x] + mch[id].cost;
                pq.push({perchance[y], y});
                last[y] = {x, id};
                // im a new soul, i came to this strange world
                // hoping i could learn a bit 'bout how to give and take
                // but since i came here
                // felt the joy and the fear
                // finding myself making every posible mistake
            }
        }
    }

    // cerr << "am iesit cu bile\n";

    for(int i = 1; i <= n; i++){
        unchii[i] = the_real_ones[i];
    }

    if(perchance[noelle] == INT_MAX){
        return 0;
    }

    // gasesc pathul
    int minim_ude = INT_MAX, nod = noelle;
    while(last[nod].second != -1){
        // cerr << "nod = " << nod << '\n';
        int id = last[nod].second;
        minim_ude = min(minim_ude, mch[id].c - mch[id].f);
        nod = last[nod].first;
    }

    // cerr << "minim_ude = " << minim_ude << '\n';
    // cerr << "perchance[noelle] = " << perchance[noelle] << " last = " << last[noelle].first << '\n';

    flux += minim_ude;
    cost += minim_ude * perchance[noelle];

    nod = noelle;
    while(nod != sursie){
        int id = last[nod].second;
        mch[id].f += minim_ude;
        mch[ mch[id].pereche ].f -= minim_ude;
        nod = last[nod].first;
    }

    return 1;
}

void fa_flux_te_rog(){
    clopot_barbat_vad();
    // cerr << "am inceput gang\n";
    // cerr << "unchii : ";
    // for(int i = 1; i <= 2 * n + 2; i++){
    //     cerr << unchii[i] << " ";
    // }
    // cerr << '\n';
    while(deschistra());
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int m; in >> n >> m;
    int intra[n + 1], iese[n + 1];
    int total = 0;

    for(int x = 1; x <= n; x++){
        for(int y = 1; y <= n; y++){
            cezar[x][y] = INT_MAX;
        }
    }

    for(int i = 1; i <= n; i++){
        intra[i] = iese[i] = 0;
        cezar[i][i] = 0;
    }

    sursie = 2 * n + 1;
    noelle = sursie + 1;

    for(int i = 0; i < m; i++){
        int x, y, c; in >> x >> y >> c;
        cryptopsy[x].push_back({c, y});
        cezar[x][y] = min(cezar[x][y], c);
        total += c;

        intra[y]++;
        iese[x]++;
    }

    for(int i = 1; i <= n; i++){
        for(int x = 1; x <= n; x++){
            for(int y = 1; y <= n; y++){
                if(cezar[x][i] != INT_MAX && cezar[i][y] != INT_MAX){
                    cezar[x][y] = min(cezar[x][y], cezar[x][i] + cezar[i][y]);
                }
            }
        }
    }

    for(int x = 1; x <= n; x++){
        for(int y = 1; y <= n; y++){
            if(cezar[x][y] != INT_MAX){
                add_muchie(x, y + n, 100000, cezar[x][y]);
                // cout << x << " " << y << " --> " << cezar[x][y] << '\n';
            }
        }
    }

    for(int i = 1; i <= n; i++){
        add_muchie(sursie, i, max(0, intra[i] - iese[i]), 0);
        add_muchie(i + n, noelle, max(0, iese[i] - intra[i]), 0);
    }

    fa_flux_te_rog();
    out << cost + total << '\n';

    return 0;
}