#include<bits/stdc++.h>

using namespace std;
#define endl "\n"
#define int long long

vector<vector<int>> arrs;
vector<vector<pair<int,int>>> adj;

void solve(){
    int n ,m;
    cin>>n>>m;
    adj = vector<vector<pair<int,int>>> (n);
    for(int i=0;i<m;i++){
        int x , y ,w;
        cin>>x>>y>>w;x--,y--;
        adj[x].push_back({y,w});
    }
    arrs = vector<vector<int>> (adj[0].size());

    for(int i =0;i<adj[0].size();i++){
        int x = 0;
        while(adj[x].size()){
            int to =adj[x][0].first;
            if(x==0) to = adj[0][i].first; 
            if(x==0) arrs[i].push_back(adj[x][i].second);
            else arrs[i].push_back(adj[x][0].second);
            x = to;
            // cout<<"??"<<endl;
        }
    }
    int get = 0;
    if(arrs.size()*arrs[0].size()!=m) assert(0);
    n = arrs.size(),m=arrs[0].size();
    for(auto&v:arrs){
        if(v.size()!=m){
            assert(0);
        }
    }
    int sm = 0;
    for(int i=0;i<n;i++){
        for(int j =0;j<m;j++){
            sm+=arrs[i][j];
            if(sm<0) assert(0);
        }
    }
    // for(int i =0;i<n;i++){
    //     sort(arrs[i].begin(),arrs[i].end());
    //     for(int  j =1;j<m;j++){
    //         arrs[i][j] -= arrs[i][0]; 
    //     }
    //     get+=arrs[i][0];
    //     arrs[i][0] = 0;
    // }

    priority_queue<pair<int,pair<int,int>>> pq;
    for(int i =0;i<n;i++){
        for(int j =0;j<m;j++){
            pq.push({arrs[i][j],{i,j}});
        }
    }
    
    int dis = sm%m;
    while(dis--){
        auto tp = pq.top();pq.pop();
        tp.first-=1;pq.push(tp);
    }
    while(pq.size()){
        auto tp = pq.top();pq.pop();
        arrs[tp.second.first][tp.second.second] = tp.first;
    }

    for(int i =0;i<n;i++){
        sort(arrs[i].begin(),arrs[i].end());
        for(int  j =1;j<m;j++){
            arrs[i][j] -= arrs[i][0]; 
        }
        get+=arrs[i][0];
        arrs[i][0] = 0;
    }

    // for(int i=0;i<n;i++){
    //     for(int j =0;j<m;j++){
    //         cout<<arrs[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    vector<deque<pair<int,int>>> vq(n);
    for(int i =0;i<n;i++){
        //数值 长度
        deque<pair<int,int>> q;
        q.push_back({0,1});
        for(int j =1;j<m;j++){
            if(arrs[i][j]==arrs[i][j-1]) q.back().second+=1;
            else q.push_back({arrs[i][j],1});
        }
        vq[i] = q;
    }

    //长度 位置
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> npq;

    for(int i=0;i<n;i++) npq.push({vq[i].front().second,i});
    int ans = 0;
    int need = sm/m;
    while(get<need){
        auto tp = npq.top();npq.pop();
        int len = tp.first ;int  pos = tp.second;
        auto f1 = vq[pos][0] ;auto  f2 = vq[pos][1];
        int add = f2.first-f1.first;
        if(get+add>=need){
            ans += f1.second*(need-get);
            get = need;
        }else{
            ans += f1.second*add;
            get+=add;
            vq[pos].pop_front();vq[pos].pop_front();
            vq[pos].push_front({f2.first,f1.second+f2.second});
            npq.push({vq[pos].front().second,pos});
        }
        if(ans<0) assert(0);
    }
    if(ans<0) assert(0);
    cout<<ans<<endl;
}
/*
8 8
1 2 1
2 3 2
3 4 2
4 8 200
1 5 0
5 6 5
6 7 0
7 8 0

4 4
1 2 0
2 4 10000
1 3 0
3 4 0

8 9
1 2 1
2 3 2
3 8 3
1 4 0
4 5 30000
5 8 3000
1 6 3
6 7 2
7 8 1

4 4
1 2 100000
2 4 100000
1 3 100000
3 4 100000

7 6
1 2 0
2 3 2
3 4 2
4 5 3
5 6 4
6 7 50

7 6
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 50

*/
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    // cin>>t;
    while(t--) 
        solve();
}