f.cpp

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair

using namespace std;
const int MAXN = 1e5 + 100;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int L = 20;
pair <int, pair <int, int> > b[MAXN];
int dsu[MAXN], h[MAXN];
int maxx[MAXN][21], up[MAXN][21];
int tin[MAXN], tout[MAXN];
vector <pair <int, int> > g[MAXN];
int ffind(int x){
    int y = x;
    while (dsu[y] != y){
        y = dsu[y];
    }
    while (dsu[x] != x){
        int z = dsu[x];
        dsu[x] = y;
        x = z;
    }
    return y;
}

void uunion(int x, int y){
    x = ffind(x);
    y = ffind(y);

    if (h[x] < h[y]){
        dsu[x] = y;
    }
    else{
        dsu[y] = x;
        if (h[x] == h[y]){
            h[x]++;
        }
    }
}
bool upper(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int timer = 0;
void dfs(int v, int pr = 0, int len = 0){
    tin[v] = ++timer;
    up[v][0] = pr;
    maxx[v][0] = len;
    for (int i = 1; i <= L; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
        maxx[v][i] = max(maxx[v][i - 1], maxx[up[v][i - 1]][i - 1]);
    }
    for (auto [to, len] : g[v]){
        if (to != pr){
            dfs(to, v, len);
        }
    }

    tout[v] = ++timer;
}
int lca(int u, int v){
    if (upper(u, v)){
        int ans = 0;
        for (int i = L; i >= 0; i--){
            if (!upper(up[v][i], u)){
                ans = max(ans, maxx[v][i]);
                v = up[v][i];
            }
        }
        return max(ans, maxx[v][0]);
    }
    if (upper(v, u)){
        int ans = 0;
        for (int i = L; i >= 0; i--){
            if (!upper(up[u][i], v)){
                ans = max(ans, maxx[u][i]);
                u = up[u][i];
            }
        }
        return max(ans, maxx[u][0]);
    }
    int ans = 0;
    for (int i = L; i >= 0; i--){
        if (!upper(up[u][i], v)){
            ans = max(ans, maxx[u][i]);
            u = up[u][i];
            //cout << "@@@ " << u << "\n";
        }
        if (!upper(up[v][i], u)){
            ans = max(ans, maxx[v][i]);
            v = up[v][i];
        }
    }
    ans = max(ans, maxx[u][0]);
    ans = max(ans, maxx[v][0]);
   // cout << "!!! " << up[u][0] << endl;
    return ans;
}


void solve(){
    tout[0] = INF;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        dsu[i] = i;
        h[i] = 1;
    }

    for (int i = 1; i <= m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        b[i] = {c, {x, y}};
    }

    sort(b + 1, b + m + 1);

    for (int i = 1; i <= m; i++){
        if (ffind(b[i].s.f) != ffind(b[i].s.s)){
            g[b[i].s.f].pb({b[i].s.s, b[i].f});
            g[b[i].s.s].pb({b[i].s.f, b[i].f});
            uunion(b[i].s.f, b[i].s.s);
        }
    }
    dfs(1);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int u, v;
        cin >> u >> v;

        cout << lca(u, v) << "\n";
    }


}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int ttt = 1;
    //cin >> ttt;
    while (ttt--){
        solve();
    }
}