#include <bits/stdc++.h>
#define rep(i, s, e) for (int i = s; i <= e; i++)
#define pii pair<int, int>
#define int long long
using namespace std;
const int MAX = 2e5 + 10;
struct Edge
{
    int nxt, c;
};
vector<Edge> E[MAX];
vector<int> path[MAX];
int n, m;
signed main()
{
    cin >> n >> m;
    rep(i, 1, m)
    {
        int x, y, z;
        cin >> x >> y >> z;
        E[x].push_back({y, z});
    }
    int tot = 0;
    rep(i, 0, (int)E[1].size() - 1)
    {
        path[i].push_back(E[1][i].c);
        for (int j = E[1][i].nxt; j != n; j = E[j][0].nxt)
        {
            path[i].push_back(E[j][0].c);
        }
    }
    rep(i, 0, (int)E[1].size() - 1)
    {
        for (int j : path[i])
            tot += j;
        sort(path[i].begin(), path[i].end());
        path[i].push_back(1e9);
    }
    int length = path[0].size() - 1, C = tot / length;
    int l = 0, r = length - 1;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        int sum = 0;
        rep(i, 0, (int)E[1].size() - 1)
        {
            sum += path[i][mid];
        }
        if (sum <= C)
        {
            l = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    int sum = 0;
    rep(i, 0, (int)E[1].size() - 1)
    {
        sum += path[i][l];
    }
    C -= sum;
    int ans = 0;
    rep(i, 0, (int)E[1].size() - 1)
    {
        for (int j = 0; path[i][j] <= path[i][l]; j++)
        {
            ans += path[i][l] - path[i][j];
        }
    }
    vector<pii> V;
    rep(i, 0, (int)E[1].size() - 1)
    {
        int j;
        for (j = 0; path[i][j] <= path[i][l]; j++)
            ;
        V.push_back({j, path[i][j] - path[i][j - 1]});
    }
    sort(V.begin(), V.end());
    rep(i, 0, (int)V.size() - 1)
    {
        C -= V[i].second;
        ans += V[i].first * V[i].second;
        if (C <= 0)
        {
            ans += V[i].first * C;
            break;
        }
    }
    cout << ans;
}