// // Created by liasa on 28/11/2025. // #include <bits/stdc++.h> using namespace std; #define ll long long #define lp(i, s, e) for (int i = s; i < e; ++i) #define v vector int k, n; v<int> in; v<ll> dist; const ll inf = 1e18; #define pll pair<ll, ll> v<v<pll>> g; void dij() { dist.resize(n, inf); priority_queue<pll, v<pll>, greater<pll>> pq; for (auto it : in) { pq.push({0, it}); dist[it] = 0; } while (!pq.empty()) { auto [d, nd] = pq.top(); pq.pop(); for (auto [it, c] : g[nd]) { if (dist[it] > c + d) { dist[it] = c + d; pq.push({c + d, it}); } } } } struct Dsu { v<ll> p, sz; Dsu() { p.resize(n); iota(p.begin(), p.end(), 0); sz.resize(n, 1); } ll find(ll v) { if (p[v] == v) return v; return p[v] = find(p[v]); } bool uni(ll a, ll b) { ll x = find(a), y = find(b); if (x == y) { return 0; } if (sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; p[y] = x; return 1; } }; struct Lca { int n, lg; v<v<int>> up; v<v<ll>> mn; v<int> dep; Lca() { n = (int)g.size(); lg = 0; while ((1 << lg) <= n) ++lg; up.assign(lg, v<int>(n)); mn.assign(lg, v<ll>(n, inf)); dep.assign(n, 0); v<int> par(n, -1); v<ll> wpar(n, inf); v<int> st; int root = 0; par[root] = root; wpar[root] = inf; dep[root] = 0; st.push_back(root); while (!st.empty()) { int vtx = st.back(); st.pop_back(); up[0][vtx] = par[vtx]; mn[0][vtx] = wpar[vtx]; for (auto [to, w] : g[vtx]) { if (to == par[vtx]) continue; par[to] = vtx; wpar[to] = w; dep[to] = dep[vtx] + 1; st.push_back(to); } } lp(k_, 1, lg) { lp(vtx, 0, n) { up[k_][vtx] = up[k_ - 1][up[k_ - 1][vtx]]; mn[k_][vtx] = min(mn[k_ - 1][vtx], mn[k_ - 1][up[k_ - 1][vtx]]); } } } ll qry(int a, int b) { if (a == b) return inf; ll res = inf; if (dep[a] < dep[b]) swap(a, b); int d = dep[a] - dep[b]; lp(k_, 0, lg) { if (d & (1 << k_)) { res = min(res, mn[k_][a]); a = up[k_][a]; } } if (a == b) return res; for (int k_ = lg - 1; k_ >= 0; --k_) { if (up[k_][a] != up[k_][b]) { res = min(res, mn[k_][a]); res = min(res, mn[k_][b]); a = up[k_][a]; b = up[k_][b]; } } res = min(res, mn[0][a]); res = min(res, mn[0][b]); return res; } }; #define tpl tuple<ll, ll, ll> int main() { ios_base::sync_with_stdio(0); cin.tie(0); int m; cin >> n >> m; g.resize(n); vector<pll> edges; vector<tpl> eg; lp(i, 0, m) { ll a, b, c; cin >> a >> b >> c; a--; b--; edges.push_back({a, b}); g[a].push_back({b, c}); g[b].push_back({a, c}); } cin >> k; lp(i, 0, k) { ll a; cin >> a; in.push_back(a - 1); } dij(); g.clear(); g.resize(n); Dsu dsu; for (auto [a, b] : edges) { eg.push_back({min(dist[a], dist[b]), a, b}); } sort(eg.begin(), eg.end()); reverse(eg.begin(), eg.end()); for (auto [c, a, b] : eg) { if (dsu.uni(a, b)) { g[a].push_back({b, c}); g[b].push_back({a, c}); } } Lca lca; int q; cin >> q; while (q--) { ll a, b; cin >> a >> b; a--; b--; ll ans = lca.qry(a, b); cout << ans << '\n'; } return 0; }