#include <bits/stdc++.h> #define int long long #define fi first #define se second #define sz(a) (int)((a).size()) #define all(a) (a).begin(), (a).end() #define lsb(x) (x & (-x)) #define vi vector<int> #define YES { cout << "YES" << endl; return; } #define NO { cout << "NO" << endl; return; } using ll = long long; using pii = std::pair<int, int>; const int NMAX = 5e5; using namespace std; struct DSU { int p[NMAX + 5]; int sz[NMAX + 5]; void init(int n) { iota(p + 1, p + n + 1, 1LL); fill(sz + 1, sz + n + 1, 1LL); } int root(int x) { if (x == p[x]) return x; return p[x] = root(p[x]); } bool same(int x, int y) { return root(x) == root(y); } void unite(int x, int y) { int rx = root(x), ry = root(y); if (sz[rx] < sz[ry]) swap(rx, ry); sz[rx] += sz[ry]; p[ry] = rx; } }; vector<pii>G[NMAX + 5]; vector<int>qu[NMAX + 5]; DSU dsu; pii srt[NMAX + 5]; int s[NMAX + 5], t[NMAX + 5], lo[NMAX + 5], hi[NMAX + 5], ans[NMAX + 5]; int dist[NMAX + 5], n, m, k, q; void dijkstra() { priority_queue<pii, vector<pii>, greater<pii>>pq; fill(dist + 1, dist + n + 1, INT_MAX); pq.push({0, 0}); while (!pq.empty()) { auto [d, nod] = pq.top(); pq.pop(); if (d > dist[nod]) continue; for (auto &[u, w] : G[nod]) { if (dist[nod] + w < dist[u]) { dist[u] = dist[nod] + w; pq.push({dist[u], u}); } } } } signed main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> m; for (int i = 0, u, v, w; i < m; ++i) { cin >> u >> v >> w; G[u].push_back({v, w}); G[v].push_back({u, w}); } cin >> k; G[0].reserve(k); for (int i = 0, g; i < k; ++i) { cin >> g; G[0].push_back({g, 0}); } dijkstra(); for (int i = 1; i <= n; ++i) srt[i] = {dist[i], i}; sort(srt + 1, srt + n + 1, std::greater()); cin >> q; for (int i = 1; i <= q; ++i) { cin >> s[i] >> t[i]; lo[i] = 1, hi[i] = n; } bool any = true; while (any) { any = false; fill(qu + 1, qu + n + 1, vector<int>()); for (int i = 1; i <= q; ++i) { if (lo[i] <= hi[i]) { int mid = (lo[i] + hi[i]) >> 1; qu[mid].push_back(i); any = true; } } dsu.init(n); for (int mid = 1; mid <= n; ++mid) { auto [d, nod] = srt[mid]; for (auto &[u, w] : G[nod]) { if (dist[u] >= d) dsu.unite(nod, u); } for (auto &idx : qu[mid]) { if (dsu.same(s[idx], t[idx])) { ans[idx] = mid; hi[idx] = mid - 1; } else lo[idx] = mid + 1; } } } for (int i = 1; i <= q; ++i) cout << srt[ans[i]].fi << '\n'; return 0; }