#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10;
//#define p first
//#define d second

int head[N], nxt[M], to[M], cap[N], cnt;
void add_edge(int u, int v, int w){
    to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt, cap[cnt] = w;
}
int n, m, sum;
vector<vector<int>> v;
void dfs(int u, vector<int>& tmp){
    for(int i = head[u]; i; i = nxt[i]){
        tmp.push_back(cap[i]);
        sum += cap[i];
        dfs(to[i], tmp);
    }
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, w;
        cin >> x >> y >> w;
        add_edge(x, y, w);
    }
    for(int i = head[1]; i; i = nxt[i]){
        vector<int> tmp;
        tmp.push_back(cap[i]);
        sum += cap[i];
        dfs(to[i], tmp);
        v.push_back(tmp);
    }
    int k = sum / v[0].size();
    vector<PII> p;
    for(int i = 0; i < v.size(); i++){
        sort(v[i].begin(), v[i].end());
        k -= v[i][0];
        for(int j = 1; j < v[i].size(); j++){
            if(v[i][j] != v[i][j - 1])
                p.push_back({j, v[i][j] - v[i][j - 1]});
        }
    }
    sort(p.begin(), p.end());
    int ans = 0;
    for(int i = 0; i < p.size(); i++){
        if(k >= p[i].second){
            ans += p[i].first * p[i].second;
            k -= p[i].second;
        }
        else{
            ans += p[i].first * k;
            break;
        }
    }
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _ = 1;
//    cin >> _;
    while(_--) solve();
    return 0;
}