#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (ll)4e18;
const int MAXN = 100000 + 5;
const int LOG = 20;
int n, m;
vector<pair<int,int>> g[MAXN];
ll dis_arr[MAXN];
struct Edge {
int u, v;
ll w;
};
vector<Edge> edges;
// DSU for Kruskal
int dsu[MAXN], dsu_sz[MAXN];
int find_set(int x){
if(dsu[x]==x) return x;
return dsu[x] = find_set(dsu[x]);
}
bool union_set(int a, int b){
a = find_set(a); b = find_set(b);
if(a==b) return false;
if(dsu_sz[a] < dsu_sz[b]) swap(a,b);
dsu[b] = a;
dsu_sz[a] += dsu_sz[b];
return true;
}
// MST adjacency (undirected)
vector<pair<int,ll>> mst[MAXN];
// HLD / LCA structures
int parentArr[MAXN];
int up[MAXN][LOG];
int depthArr[MAXN];
int sz[MAXN];
int ChainHead[MAXN], ChainID[MAXN], posInBase[MAXN], baseArr[MAXN];
int CurChain = 0, CurPos = 0;
ll aVal[MAXN]; // stores dis value for each node
// segment tree (min)
vector<ll> seg;
int baseN = 0;
void dijkstra_multi_source(const vector<int>& srcs){
for(int i=1;i<=n;i++) dis_arr[i] = INFLL;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
for(int s: srcs){
dis_arr[s] = 0;
pq.push({0, s});
}
while(!pq.empty()){
auto cur = pq.top(); pq.pop();
ll d = cur.first; int u = cur.second;
if(d != dis_arr[u]) continue;
for(auto &e : g[u]){
int v = e.first; int w = e.second;
if(dis_arr[v] > d + w){
dis_arr[v] = d + w;
pq.push({dis_arr[v], v});
}
}
}
}
// DFS to prepare sizes, up[v][0], depth, parentArr
void dfs_prep(int u, int p){
parentArr[u] = p;
up[u][0] = p;
sz[u] = 1;
for(auto &e : mst[u]){
int v = e.first;
ll w = e.second; // weight stored but we use aVal for node values
if(v == p) continue;
depthArr[v] = depthArr[u] + 1;
dfs_prep(v, u);
sz[u] += sz[v];
}
}
// HLD: assign chain/head/pos/baseArr
void HLD(int u, int p){
if(ChainHead[CurChain] == 0) ChainHead[CurChain] = u;
ChainID[u] = CurChain;
posInBase[u] = ++CurPos;
baseArr[CurPos] = u;
int heavy = -1;
for(auto &e : mst[u]){
int v = e.first;
if(v == p) continue;
if(heavy == -1 || sz[v] > sz[heavy]) heavy = v;
}
if(heavy != -1) HLD(heavy, u);
for(auto &e : mst[u]){
int v = e.first;
if(v == p || v == heavy) continue;
CurChain++;
HLD(v, u);
}
}
// segment tree helpers
void seg_init(int nbase){
baseN = nbase;
seg.assign(4 * (baseN+5), INFLL);
}
void seg_build(int id, int l, int r){
if(l == r){
int node = baseArr[l];
seg[id] = aVal[node];
return;
}
int mid = (l+r)/2;
seg_build(id*2, l, mid);
seg_build(id*2+1, mid+1, r);
seg[id] = min(seg[id*2], seg[id*2+1]);
}
ll seg_query(int id, int l, int r, int ql, int qr){
if(ql > r || qr < l) return INFLL;
if(ql <= l && r <= qr) return seg[id];
int mid = (l+r)/2;
return min(seg_query(id*2, l, mid, ql, qr), seg_query(id*2+1, mid+1, r, ql, qr));
}
// LCA (binary lifting) - requires up[][] precomputed
int lca(int u, int v){
if(depthArr[u] < depthArr[v]) swap(u,v); // u deeper
int diff = depthArr[u] - depthArr[v];
for(int j=0;j<LOG;j++){
if(diff & (1<<j)) u = up[u][j];
}
if(u == v) return u;
for(int j=LOG-1;j>=0;j--){
if(up[u][j] != up[v][j]){
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
// Query min of aVal on path u--v excluding LCA node itself (matches original HLD intention)
// Returns INFLL if no nodes considered (e.g., u==v)
ll query_path_min_exclude_lca(int u, int v){
int p = lca(u,v);
ll ans = INFLL;
// bring u up to p, chain by chain
while(ChainID[u] != ChainID[p]){
int head = ChainHead[ChainID[u]];
ans = min(ans, seg_query(1, 1, baseN, posInBase[head], posInBase[u]));
// jump to parent of head
u = up[head][0];
}
// same chain: exclude p itself
if(posInBase[p] + 1 <= posInBase[u]){
ans = min(ans, seg_query(1, 1, baseN, posInBase[p] + 1, posInBase[u]));
}
// bring v up to p
while(ChainID[v] != ChainID[p]){
int head = ChainHead[ChainID[v]];
ans = min(ans, seg_query(1, 1, baseN, posInBase[head], posInBase[v]));
v = up[head][0];
}
if(posInBase[p] + 1 <= posInBase[v]){
ans = min(ans, seg_query(1, 1, baseN, posInBase[p] + 1, posInBase[v]));
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i=1;i<=n;i++){
g[i].clear();
mst[i].clear();
}
for(int i=0;i<m;i++){
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
int k;
cin >> k;
vector<int> sources(k);
for(int i=0;i<k;i++) cin >> sources[i];
// multi-source dijkstra
dijkstra_multi_source(sources);
// build edges with weight = min(dist[u], dist[v]) (only once per undirected edge)
edges.clear();
for(int u=1; u<=n; u++){
for(auto &e : g[u]){
int v = e.first;
if(u < v){
edges.push_back({u, v, min(dis_arr[u], dis_arr[v])});
}
}
}
sort(edges.begin(), edges.end(), [](const Edge &A, const Edge &B){
return A.w > B.w; // maximum spanning
});
// init dsu
for(int i=1;i<=n;i++){
dsu[i] = i; dsu_sz[i] = 1;
}
// Kruskal -> MST (maximum spanning forest)
for(auto &e : edges){
if(union_set(e.u, e.v)){
mst[e.u].push_back({e.v, e.w});
mst[e.v].push_back({e.u, e.w});
}
}
// prepare arrays
for(int i=1;i<=n;i++){
parentArr[i] = 0;
depthArr[i] = 0;
sz[i] = 0;
for(int j=0;j<LOG;j++) up[i][j] = 0;
ChainHead[i] = 0;
ChainID[i] = 0;
posInBase[i] = 0;
baseArr[i] = 0;
aVal[i] = dis_arr[i]; // node value
}
CurChain = 1; CurPos = 0;
// run DFS prep and HLD for all components (forest)
for(int i=1;i<=n;i++){
if(depthArr[i] == 0){
depthArr[i] = 1;
dfs_prep(i, 0);
HLD(i, 0);
CurChain++;
}
}
// build binary lifting up[][] using parentArr (we set up[][0] = parentArr)
// note: up[][] currently has up[v][0] = parentArr[v] = set in dfs_prep (which used parent)
for(int j=1;j<LOG;j++){
for(int v=1; v<=n; v++){
int mid = up[v][j-1];
if(mid == 0) up[v][j] = 0;
else up[v][j] = up[mid][j-1];
}
}
// build segtree on base size = CurPos
int bN = CurPos;
if(bN == 0){
// no nodes? safety
bN = n;
}
seg_init(bN);
seg_build(1, 1, bN);
// queries
int Qq;
cin >> Qq;
while(Qq--){
int u,v; cin >> u >> v;
// if u and v not in same MST component, there's no path in the MST
if(find_set(u) != find_set(v)){
cout << -1 << '\n';
continue;
}
ll ans = query_path_min_exclude_lca(u, v);
if(ans == INFLL) cout << -1 << '\n';
else cout << ans << '\n';
}
return 0;
}
