// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define el "\n" #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define mp make_pair #define sqr(x) ((x) * (x)) #define FOR(i, l, r) for (int i = l; i <= (r); i++) #define FOD(i, l, r) for (int i = l; i >= (r); i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) ((int)(x).size()) #define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); using db = long double; using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vll = vector<ll>; using vpii = vector<pii>; using vpll = vector<pll>; using vvi = vector<vi>; using vvll = vector<vll>; using vbool = vector<bool>; using vvbool = vector<vbool>; template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); } template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); } // #define DEBUG #ifdef DEBUG #include "D:\cpp\debug.h" #else #define debug(...) #define debug_arr(...) #endif mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); constexpr int N = 1E5 + 5; constexpr int INF = 1E9 + 7; constexpr ll INFLL = 4E18; constexpr int MOD = 1E9 + 7; // 998244353 constexpr double EPS = 1E-10; struct DSU { vi parent, size; DSU(int n): parent(n + 1), size(n + 1, 1) { iota(all(parent), 0); } int find(int u) { return u == parent[u] ? u : parent[u] = find(parent[u]); } bool join(int u, int v) { u = find(u), v = find(v); if (u == v) return false; if (size[u] < size[v]) swap(u, v); parent[v] = u; size[u] += size[v]; return true; } }; vpii adj[N]; pii queries[N], sorted[N]; int low[N], high[N], res[N]; int dist[N]; int n, m, k, q; void solve() { cin >> n >> m; while (m--) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } cin >> k; fill(all(dist), INF); priority_queue<pii, vpii, greater<pii>> pq; while (k--) { int x; cin >> x; pq.emplace(0, x); dist[x] = 0; } while (!pq.empty()) { auto state = pq.top(); pq.pop(); auto [d, u] = state; if (d != dist[u]) continue; for (auto &[v, w] : adj[u]) { if (chmin(dist[v], dist[u] + w)) { pq.emplace(dist[v], v); } } } FOR(i, 1, n) { sorted[i] = {dist[i], i}; } sort(sorted + 1, sorted + n + 1, greater<pii>()); cin >> q; FOR(i, 1, q) { int s, t; cin >> s >> t; queries[i] = {s, t}; low[i] = 1; high[i] = n; } for (;;) { vvi bucket(n + 2); bool changed = false; FOR(i, 1, q) { if (low[i] <= high[i]) { int mid = (low[i] + high[i]) / 2; bucket[mid].push_back(i); changed = true; } } if (!changed) break; DSU dsu(n); FOR(i, 1, n) { auto [d, u] = sorted[i]; for (auto &[v, _] : adj[u]) { if (dist[v] >= d) { dsu.join(u, v); } } for (int id : bucket[i]) { auto [s, t] = queries[id]; if (dsu.find(s) == dsu.find(t)) { res[id] = i; high[id] = i - 1; } else { low[id] = i + 1; } } } } FOR(i, 1, q) { cout << sorted[res[i]].fi << el; } } int main() { fast_io #define LOCAL #ifndef LOCAL #define PROBLEM "" freopen(PROBLEM ".INP", "r", stdin); freopen(PROBLEM ".OUT", "w", stdout); #endif int t = 1; // cin >> t; while (t--) solve(); }