#include <bits/stdc++.h>

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPL(i, j, n) for (int i = (j); i < (n); ++i)
#define sz(X) ((int)(X).size())
using namespace std;
#define int long long

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vi> vvi;
int solve() {
    int n,m;cin>>n>>m;
    vvii adj(n);
    REP(i, m) {
        int x,y,z;cin>>x>>y>>z;x--;y--;
        adj[x].push_back({y,z});
    }
    vvi comps;
    for (auto [v,w]: adj[0]) {
        vi comp;
        comp.push_back(w);
        int cur = v;
        while (cur != n-1) {
            auto [nxt, wi] = adj[cur][0];
            comp.push_back(wi);
            cur = nxt;
        }
        comps.push_back(comp);

    } 
    int chains = sz(comps);
    int len = sz(comps[0]);
    vector<map<int,int>> ctarr(chains);

    vi currentthres(chains);
    vi currentsmaller(chains);
    set<ii> excesses;

    int currentans = 0;
    int flowexcess = 0;
    REP(i, chains) {
        vi &vec = comps[i];
        int g1 = accumulate(vec.begin(), vec.end(), 0LL);
        //cout<<g1<<"..\n";
        int mn = g1/len;
        currentthres[i] = mn;
        for (auto x: vec) {
            ctarr[i][x]++;
            if (x < mn) {
                currentans += mn - x;
                currentsmaller[i]++;
            }
        }
        flowexcess += g1%len;
    }
    REP(i, chains) {
        int tocull = ctarr[i][currentthres[i]];
        currentthres[i]++;
        currentsmaller[i] += tocull;
        excesses.insert({currentsmaller[i], i});
    }
    REP(i, flowexcess/len) {
        auto [hw, idx] = *excesses.begin();
        excesses.erase(excesses.begin());
        currentans += hw;
        int tocull = ctarr[idx][currentthres[idx]];
        currentthres[idx]++;
        currentsmaller[idx] += tocull;
        excesses.insert({currentsmaller[idx], idx});
    }
    return currentans;

}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc = 1;
    REP(i, tc) {
        cout<<solve()<<"\n";
    }
}