#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; typedef long long ll; #define st first #define nd second #define f(a, c, b) for (int a = c; b > a; a++) #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) int(a.size()) #define int ll #define DUZO 1000000000000000000 using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vvi = vector<vector<int>>; vector<vector<pii>> g; vi sajz; vi szef; vi ak; int find(int v) { if (szef[v] == v) return v; return (szef[v] = find(szef[v])); } void un(int v, int u) { //la szef[v] = find(v); szef[u] = find(u); if (szef[u] == szef[v]) { return; } if (sajz[szef[v]] < sajz[szef[u]]) swap(u, v); sajz[szef[v]] += sajz[szef[u]]; szef[szef[u]] = szef[v]; } void doc(int v) { //aktywujemy ten wierzcholek sajz[v] = 1; szef[v] = v; ak[v] = 1; for (pii u: g[v]) { if (!ak[u.st]) continue; un(u.st, v); } } void solve() { int n, m, k, q; cin >> n >> m; g.resize(n + 1); f(i, 0, m) { int u, v, w; cin >> u >> v >> w; g[u].pb({v, w}); g[v].pb({u, w}); } vector<pii> kol; //kolejnosc w zbiorowej dijkstrze priority_queue<pii> djk; cin >> k; vi nnp(k); f(i, 0, k) cin >> nnp[i]; f(i, 0, k) { djk.push({0, nnp[i]}); } vi odw(n + 1, 0); while (sz(djk)) { pii p1 = djk.top(); djk.pop(); int v = p1.nd; int koszt = -p1.st; if (odw[v]) continue; odw[v] = 1; kol.pb({koszt, v}); for (pii u: g[v]) { if (!odw[u.st]) { djk.push({-(koszt + u.nd), u.st}); } } } cin >> q; vector<pair<int, int>> pyt(q); f(i, 0, q) cin >> pyt[i].st >> pyt[i].nd; vector<pair<int, int>> pbs(q, {0, 100000007}); vi ans(q, -1); int ile_zrobione = 0; sajz.resize(n + 1); szef.resize(n + 1); ak.resize(n + 1); while (ile_zrobione < q) { f(i, 1, n + 1) ak[i] = 0; priority_queue<pii> zm; //pseudo miotla for (pii ele: kol) { zm.push(ele); } f(i, 0, q) { if (pbs[i].st != pbs[i].nd) { zm.push({(pbs[i].st + pbs[i].nd + 1)/2, i - (q + 2)}); } } while (sz(zm)) { pii p1 = zm.top(); zm.pop(); int ind = p1.nd; if (ind < 0) { ind += (q + 2); int s = pyt[ind].st; int t = pyt[ind].nd; if (ak[s] && ak[t]) { if (find(s) == find(t)) { //da sie dotrzec pbs[ind].st = p1.st; if (pbs[ind].st == pbs[ind].nd) { ans[ind] = pbs[ind].nd; ile_zrobione++; } } else { pbs[ind].nd = p1.st - 1; if (pbs[ind].st == pbs[ind].nd) { ile_zrobione++; ans[ind] = pbs[ind].st; } else { zm.push({(pbs[ind].st + pbs[ind].nd + 1)/2, ind - (q + 2)}); } } } else { pbs[ind].nd = p1.st - 1; if (pbs[ind].st == pbs[ind].nd) { ile_zrobione++; ans[ind] = pbs[ind].st; } else { zm.push({(pbs[ind].st + pbs[ind].nd + 1)/2, ind - (q + 2)}); } } } else { doc(ind); } } } f(i, 0, q) { cout << ans[i] << "\n"; } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int q = 1; //cin >> q; while (q--) solve(); return 0; }