与えられるグラフにおいて、重みが \(n\) 以下である辺のみを残したグラフを \(G_n\) とおきます。

元のグラフにおける \(d(S_j,T_j)\) の値を \(D_j\) とします。また、元のグラフにおいて頂点 \(S_j\) と頂点 \(T_j\) を結ぶパスのうち、「パス上の辺の重みの最大値」が \(D_j\) に等しいようなパスの集合を \(\mathcal P\) とします。

• \(W_{A_j} > D_j\) のとき : 任意の \(P \in \mathcal P\) について、\(P\) は辺 \(A_j\) を含まないので、辺 \(A_j\) の重みが増えても \(P\) 上の辺の重みの最大値は変わらず \(D_j\) です。したがって \(d(S_j,T_j)\) も変化しません。

• \(W_{A_j} < D_j\) のとき : 辺 \(A_j\) の重みが \(1\) 増えても \(W_{A_j} \leq D_j\) であるため、任意の \(P \in \mathcal P\) について、 (\(P\) が辺 \(A_j\) を含むかどうかに関わらず) \(P\) 上の辺の重みの最大値は変わらず \(D_j\) です。したがって \(d(S_j,T_j)\) も変化しません。

• \(W_{A_j} = D_j\) のとき : 辺 \(A_j\) を含まないようなパス \(P \in \mathcal P\) が存在するならば、\(P\) 上の辺の重みの最大値は変わらず \(D_j\) なので、 \(d(S_j,T_j)\) は変化しません。逆に、全ての \(P \in \mathcal P\) について \(P\) が辺 \(A_j\) を含むならば、\(d(S_j,T_j)\) の値は \(1\) 増加します。

\(W_{A_j}\) と \(D_j\) の大小関係については、\(G_{W_{A_j}}\) および \(G_{W_{A_j}-1}\) において頂点 \(S_j\) と頂点 \(T_j\) が連結であるかどうかが分かればよいので、union-find を使うことで簡単に求められます。

残る課題は、\(W_{A_j} = D_j\) を満たす各クエリについて、辺 \(A_j\) を含まないようなパス \(P \in \mathcal P\) が存在するかどうかを判定することです。ここで、「辺 \(A_j\) を含まないようなパス \(P \in \mathcal P\) が存在しない」という条件は以下のように言い換えられます。

• \(G_{W_{A_j}}\) において、重みが \(W_{A_j}\) 未満の辺をすべて縮約したグラフを考える。このグラフにおいて辺 \(A_j\) は橋であり、辺 \(A_j\) を削除したときに新たにできる \(2\) つの連結成分の一方に頂点 \(S_j\) が、もう一方に頂点 \(T_j\) が含まれる。

ただし、グラフにおける橋とは、その辺を削除すると連結成分の数が増えるような辺のことを指す用語です。頂点数 \(V\)、辺数 \(E\) のグラフが与えられたとき、そのグラフ上の橋を列挙する問題は、lowlink とよばれるアルゴリズムによって \(O(V+E)\) で解くことができます。

よって、「\(G_{W_{A_j}}\) において、重みが \(W_{A_j}\) 未満の辺をすべて縮約したグラフ」において、

• 辺 \(A_j\) が橋であるかどうか
• 辺 \(A_j\) が橋であるならば、辺 \(A_j\) を削除したときに新たにできる \(2\) つの連結成分の一方に頂点 \(S_j\) が、もう一方に頂点 \(T_j\) が含まれるかどうか

を判定すればよいです。前者は lowlink で、後者は DFS-order を用いることで高速に判定可能です。よって本問題を解くことができました。計算量は、下記の実装例では \(O(N+M\alpha (N) + Q\log Q +(M+Q) \log M)\) になります。

おまけ：計算量は悪化しますが、lowlink の部分は ABC295-G と同様のアルゴリズムによって代替可能です。

実装例 (C++) :

#include<bits/stdc++.h>
#include "atcoder/dsu"

using namespace std;
using namespace atcoder;

class lowlink {
    int n;
    vector<vector<pair<int, int>>> G;
    vector<int> in, out, low;
    unordered_map<int, int> bridge;
    
    void dfs(int u, int p, int &k) {
        in[u] = low[u] = k++;
        for (auto [v, id]: G[u]) {
            if (in[v] < 0) {
                dfs(v, id, k);
                low[u] = min(low[u], low[v]);
                if (low[v] > in[u]) bridge[id] = v;
            } else if (id != p) {
                low[u] = min(low[u], in[v]);
            }
        }
        out[u] = k;
    }
    
    void init() {
        n = G.size();
        in.assign(n, -1);
        out.assign(n, -1);
        low.assign(n, -1);
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (in[i] < 0) dfs(i, -1, k);
        }
    }

public:
    lowlink(const vector<vector<pair<int, int>>> &G) : G(G) { init(); }
    
    bool query(int a, int s, int t) {
        assert(0 <= s and s < n);
        assert(0 <= t and t < n);
        assert(s != t);
        if (!bridge.count(a)) return false;
        int l = in[bridge[a]], r = out[bridge[a]];
        s = in[s], t = in[t];
        return (l <= s and s < r) xor (l <= t and t < r);
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m), w(m);
    vector<vector<int>> weight(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        --u[i], --v[i], --w[i];
        weight[w[i]].push_back(i);
    }
    int q;
    cin >> q;
    vector<int> a(q), s(q), t(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> s[i] >> t[i];
        --a[i], --s[i], --t[i];
    }
    vector<int> ans(q, -1);
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return w[a[i]] < w[a[j]]; });
    
    // 元々の d(s[j], t[j]) が w[a[j]] と一致しないクエリを処理
    dsu uf(n);
    int l = 0;
    for (int i = 0; i < m; i++) {
        int r = l;
        while (r < q and w[a[ord[r]]] == i) ++r;
        for (int j = l; j < r; j++) {
            if (uf.same(s[ord[j]], t[ord[j]])) ans[ord[j]] = 0;
        }
        for (int j: weight[i]) {
            uf.merge(u[j], v[j]);
        }
        for (int j = l; j < r; j++) {
            if (!uf.same(s[ord[j]], t[ord[j]])) ans[ord[j]] = 0;
        }
        l = r;
    }
    
    uf = dsu(n);
    int it = 0;
    for (int i = 0; i < m; i++) {
        vector<int> ls; // 現在の連結成分のうち重み i の辺と接続しているものの代表元の集合
        for (int j: weight[i]) {
            ls.push_back(uf.leader(u[j]));
            ls.push_back(uf.leader(v[j]));
        }
        sort(ls.begin(), ls.end());
        ls.erase(unique(ls.begin(), ls.end()), ls.end());
        int sz = ls.size();
        vector<vector<pair<int, int>>> G(sz); // edge = (to, id)
        for (int j: weight[i]) {
            int nu = lower_bound(ls.begin(), ls.end(), uf.leader(u[j])) - ls.begin();
            int nv = lower_bound(ls.begin(), ls.end(), uf.leader(v[j])) - ls.begin();
            if(nu != nv) {
                G[nu].emplace_back(nv, j);
                G[nv].emplace_back(nu, j);
            }
        }
        lowlink lk(G);
        while (it < q and w[a[ord[it]]] == i) {
            int now = ord[it++];
            if (ans[now] != -1) continue;
            int ns = lower_bound(ls.begin(), ls.end(), uf.leader(s[now])) - ls.begin();
            int nt = lower_bound(ls.begin(), ls.end(), uf.leader(t[now])) - ls.begin();
            assert(ns != nt);
            assert(ns < sz and nt < sz);
            assert(ls[ns] == uf.leader(s[now]) and ls[nt] == uf.leader(t[now]));
            // G 上において、ns-nt パスは必ず辺 a[now] を含むかどうか判定
            ans[now] = lk.query(a[now], ns, nt);
        }
        for (int j: weight[i]) {
            uf.merge(u[j], v[j]);
        }
    }
    
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}