Untitled

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

constexpr int maxN = 1e5;
constexpr int K = 320;

struct mexsd {
    
    set<int> mex[K];
    vector<int> cnt;

    mexsd() {
        cnt.assign(maxN + 1, 0);
        for (int i = 0; i < K; i++) {
            int L = i * K, R = (i + 1) * K;
            for (int j = L; j < R; j++) {
                mex[i].insert(j);
            }
        }
    }

    void add(int x) {
        if (x > maxN) return;
        cnt[x]++;
        if (cnt[x] == 1) {
            mex[x / K].erase(x);
        }
    }

    void remove(int x) {
        if (x > maxN) return;
        cnt[x]--;
        if (cnt[x] == 0) {
            mex[x / K].insert(x);
        }
    }

    int get_mex() {
        for (int i = 0; i < K; i++) {
            if (!mex[i].empty()) {
                return *mex[i].begin();
            }
        }
        assert(false);
    }

};

struct query {
    int l, r, t;
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        u--; v--;
        graph[u].emplace_back(v, x);
        graph[v].emplace_back(u, x);
    }
    vector<pair<int, int>> euler;
    euler.emplace_back(0, INT_MAX);
    auto dfs = [&](auto self, int v, int p) -> void {
        for (auto &[g, e] : graph[v]) {
            if (g != p) {
                euler.emplace_back(g, e);
                self(self, g, v);
                euler.emplace_back(v, e);
            }
        }
    };
    dfs(dfs, 0, -1);
    vector<int> p(n, -1);
    for (int i = 0; i < (int)euler.size(); i++) {
        if (p[euler[i].first] == -1) {
            p[euler[i].first] = i;
        }
    }
    vector<query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--; queries[i].r--;
        queries[i].l = p[queries[i].l];
        queries[i].r = p[queries[i].r];
        queries[i].t = i;
    }
    sort(queries.begin(), queries.end(), [&](query &lhs, query &rhs) {
        return lhs.r / K < rhs.r / K || (lhs.r / K == rhs.r / K && lhs.l * (lhs.r / K % 2 ? -1 : 1) < rhs.l * (rhs.r / K % 2 ? -1 : 1));
    });
    vector<bool> way(n, false);
    way[0] = true;
    int l = 0, r = 0;
    // [l, r] in euler
    mexsd sd;
    vector<int> ans(q);
    for (auto &[ql, qr, t] : queries) {
        while (ql < l) {
            pair<int, int> nxtp = euler[l - 1];
            pair<int, int> curp = euler[l];
            if (way[nxtp.first]) {
                way[curp.first] = false;
                sd.remove(curp.second);
            } else {
                way[nxtp.first] = true;
                sd.add(nxtp.second);
            }
            l--;
        }
        while (qr > r) {
            pair<int, int> nxtp = euler[r + 1];
            pair<int, int> curp = euler[r];
            if (way[nxtp.first]) {
                way[curp.first] = false;
                sd.remove(curp.second);
            } else {
                way[nxtp.first] = true;
                sd.add(nxtp.second);
            }
            r++;
        }
        while (ql > l) {
            pair<int, int> nxtp = euler[l + 1];
            pair<int, int> curp = euler[l];
            if (way[nxtp.first]) {
                way[curp.first] = false;
                sd.remove(curp.second);
            } else {
                way[nxtp.first] = true;
                sd.add(nxtp.second);
            }
            l++;
        }
        while (qr < r) {
            pair<int, int> nxtp = euler[r - 1];
            pair<int, int> curp = euler[r];
            if (way[nxtp.first]) {
                way[curp.first] = false;
                sd.remove(curp.second);
            } else {
                way[nxtp.first] = true;
                sd.add(nxtp.second);
            }
            r--;
        }
        debug(way);
        ans[t] = sd.get_mex();
    }
    for (int &i : ans) {
        cout << i << '\n';
    }
}

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