B

#include <bits/stdc++.h>
using namespace std;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    struct Edge {
        int u, v, ql, qr, length;
    };
    int n, q;
    cin >> n >> q;
    vector<int> ask(q+1, -888), ans(q+1, -999);
    vector<pair<int,int>> seen(n+1); // {dfs_id, start_id}
    vector<int> is_key(n+1); // {dfs_id}
    vector<int> keys_in_subtree(n+1); // {dfs_id}
    vector<pair<Edge,int>> up(n+1); // {edge, dfs_id}
    vector<pair<vector<Edge>,int>> down(n+1); // {edges, dfs_id}
    int dfs_id = 0;
    auto go = [&] (auto f, int tl, int tr, vector<Edge> edges) -> void {
        dfs_id += 1;
        int tm = (tl + tr) >> 1;
        for (int i = tl; i <= tr; i += 1) {
            is_key[ask[i]] = dfs_id;
        }
        vector<int> start_from;
        vector<Edge> to_l, to_r;
        for (const auto &[u, v, l, r, length] : edges) {
            if (l<=tl&&tr<=r) {
                up[u] = {{u,v,l,r,length}, dfs_id};
                start_from.push_back(u);
                if (down[v].second != dfs_id) {
                    down[v].second = dfs_id;
                    down[v].first.clear();
                }
                if (down[u].second != dfs_id) {
                    down[u].second = dfs_id;
                    down[u].first.clear();
                }
                down[v].first.push_back({u,v,l,r,length});
            } else {
                is_key[u] = dfs_id;
                is_key[v] = dfs_id;
                if (l <= tm) {
                    to_l.push_back({u,v,l,min(r,tm),length});
                }
                if (r >= tm+1) {
                    to_r.push_back({u,v,max(l, tm+1),r,length});
                }
            }
        }
        vector<int> roots;
        for (const auto &x : start_from) {
            int y = x;
            if (seen[y].first == dfs_id) {
                continue;
            }
            while (true) {
                seen[y] = {dfs_id, x};
                if (up[y].second != dfs_id || seen[up[y].first.v] == seen[y]) {
                    roots.push_back(y);
                    break;
                }
                if (seen[up[y].first.v].first == dfs_id) {
                    break;
                }
                y = up[y].first.v;
            }
        }
        auto find_keys = [&] (auto f, int u, int rt) -> bool {
            bool ret = is_key[u] == dfs_id;
            for (const auto &x : down[u].first) {
                if (x.u != rt) {
                    ret |= f(f, x.u, rt);
                }
            }
            if (ret) {
                keys_in_subtree[u] = dfs_id;
            }
            return ret;
        };
        for (const auto &x : roots) {
            find_keys(find_keys, x, x);
        }
        for (const auto &x : roots) {
            if (keys_in_subtree[x] == dfs_id && up[x].second == dfs_id) {
                is_key[up[x].first.v] = dfs_id; // asking not to skip this node
            }
        }
        for (const auto &x : roots) {
            find_keys(find_keys, x, x);
        }
        auto dfs = [&] (auto f, int u, int rt) -> pair<int,int> /* length, destination */ {
            vector<pair<int,int>> children;
            for (const auto &x : down[u].first) {
                if (x.u != rt && keys_in_subtree[x.u] == dfs_id) {
                    pair<int,int> z = f(f, x.u, rt);
                    z.first += x.length;
                    children.push_back(z);
                }
            }
            if (children.size() > 1 || is_key[u] == dfs_id || u == rt) {
                for (const auto &[l, dest] : children) {
                    to_l.push_back({dest, u, tl, tm, l});
                    to_r.push_back({dest, u, tm+1, tr, l});
                }
                return {0, u};
            }
            if (children.size()) {
                return children.front();
            }
            return {0, u};
        };
        for (const auto &x : roots) {
            if (keys_in_subtree[x] == dfs_id) {
                dfs(dfs, x, x);
                if (up[x].second == dfs_id) {
                    to_l.push_back({x, up[x].first.v, tl, tm, up[x].first.length});
                    to_r.push_back({x, up[x].first.v, tm+1, tr, up[x].first.length});
                }
            }
        }
        if (tl == tr) {
            int y = ask[tl];
            ans[tl] = 0;
            dfs_id += 1;
            while (seen[y].first != dfs_id) {
                seen[y].first = dfs_id;
                ans[tl] += up[y].first.length;
                y = up[y].first.v;
            }
            return;
        }
        f(f, tl, tm, to_l);
        f(f, tm+1, tr, to_r);
    };
    vector<int> added_at_time(n+1, 1);
    vector<int> edge_to(n+1);
    iota(edge_to.begin(), edge_to.end(), 0ll);
    vector<Edge> edges;
    for (int i = 1; i <= q; i += 1) {
        int pos, val;
        cin >> pos >> val >> ask[i];
        if (added_at_time[pos] <= i-1) {
            edges.push_back({pos, edge_to[pos], added_at_time[pos], i-1, 1});
        }
        edge_to[pos] = val;
        added_at_time[pos] = i;
    }
    for (int pos = 1; pos <= n; pos += 1) {
        edges.push_back({pos, edge_to[pos], added_at_time[pos], q, 1});
    }
    go(go, 1, q, edges);
    for (int i = 1; i <= q; i += 1) {
        cout << ans[i] << "\n";
    }
}