#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]);
    vi excesses;
    int currentans = 0;
    int flowexcess = 0;
    for (auto vec: comps) {

        int g1 = accumulate(vec.begin(), vec.end(), 0LL);
        //cout<<g1<<"..\n";
        int mn = g1/len;
        int d1 = 0;
        int d2 = 0;
        for (auto x: vec) {
            d1 += max(0LL, mn - x);
            d2 += max(0LL, mn + 1 - x);
        }
        excesses.push_back(d2 - d1);
        flowexcess += g1%len;
        currentans += d1;
    }
    sort(excesses.begin(), excesses.end());
    REP(i, flowexcess/len) {
        currentans += excesses[i];
    }
    return currentans;

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