123321312

//Слава Україні, Героям слава

#include <bits/stdc++.h>

using namespace std;

int t, n, l, q;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> up, ans;
vector<int> tin, tout, h;

void dfs(int v, int w = INT_MAX, int p = 1, int hh = 0) {
    tin[v] = ++t;
    up[v][0] = p;
    ans[v][0] = w;
    for (int i = 1; i <= l; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
        ans[v][i] = min(ans[v][i - 1], ans[up[v][i - 1]][i - 1]);
    }
    for (auto u : adj[v]) {
        if (u.first != p) {
            dfs(u.first, u.second, v, hh + 1);
        }
    }
    h[v] = hh;
    tout[v] = ++t;
}

bool isanc(int u, int v) {
    return tin[u] <= tin[v] and tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (isanc(u, v)) {
        return u;
    }
    if (isanc(v, u)) {
        return v;
    }
    for (int i = l; i >= 0; i--) {
        if (!isanc(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}

int dist(int u, int v) {
    int k = lca(u, v);
    return abs(h[u] - h[k]) + abs(h[v] - h[k]);
}

int calc(int a, int b) {
    int k = lca(a, b);
    int d1 = h[a] - h[k];
    int d2 = h[b] - h[k];
    int res = INT_MAX;
    int cnt = 0;
    while(d1) {
        if(d1 & 1) {
            res = min(res, ans[a][cnt]);
            a = up[a][cnt];
        }
        d1 >>= 1;
        cnt++;
    }
    cnt = 0;
    while(d2) {
        if(d2 & 1) {
            res = min(res, ans[b][cnt]);
            b = up[b][cnt];
        }
        d2 >>= 1;
        cnt++;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m;
    l = ceil(log2(n + 1)) + 1;
    tin.resize(n + 1); tout.resize(n + 1); h.resize(n + 1);
    adj.resize(n + 1); up.assign(n + 1, vector<int>(l + 1)); ans.assign(n + 1, vector<int>(l + 1));
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    dfs(1);
    cin >> q;
    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << calc(a, b) << "\n";
    }
    return 0;
}