#include <iostream> #include <vector> #include <utility> #include <queue> #include <algorithm> #define int long long #define pii pair<int,int> #define x first #define y second using namespace std; int n,m,k,q,x,y,z,dp[100005]; vector <pii> v[100005]; priority_queue < pii, vector<pii>, greater<pii> > pq; inline void bfs() { while(!pq.empty()) { auto [d,p]=pq.top(); pq.pop(); if(d>dp[p]) continue; for(auto [i,c] : v[p]) if(dp[p]+c<dp[i]) { dp[i]=dp[p]+c; pq.push({dp[i],i}); } } } struct edge { int x,y,z; bool operator<(const edge &a) const { return z>a.z; } }; int p[100005]; inline int find(int x) { if(p[x]<0) return x; return p[x]=find(p[x]); } inline void uneste(int x, int y) { int px=find(x); int py=find(y); if(p[px]<p[py]) { p[px]+=p[py]; p[py]=px; } else { p[py]+=p[px]; p[px]=py; } } vector <edge> e; vector <pii> u[100005]; inline void build_tree() { for(int i=0; i<e.size(); i++) e[i].z=min(dp[e[i].x],dp[e[i].y]); sort(e.begin(), e.end()); for(int i=0; i<e.size(); i++) if(find(e[i].x)!=find(e[i].y)) { uneste(e[i].x,e[i].y); u[e[i].x].emplace_back(e[i].y,e[i].z); u[e[i].y].emplace_back(e[i].x,e[i].z); } } int depth[100005]; pii par[22][100005]; inline void dfs(int nod, int p, int c,int val) { depth[nod]=val; par[0][nod]={p,c}; for(auto [i,c] : u[nod]) if(i!=p) dfs(i,nod,c,val+1); } inline void precalc() { for(int i=0; i<=n; i++) par[0][i]={0,(1LL<<60)}; dfs(1,0,(1LL<<60),1); for(int i=1; i<=20; i++) for(int j=0; j<=n; j++) par[i][j]={par[i-1][par[i-1][j].x].x, min(par[i-1][j].y,par[i-1][par[i-1][j].x].y)}; } inline int jump(int &x, int k) { int rez=(1LL<<60); for(int i=20; i>=0; i--) if((1<<i) & k) rez=min(rez,par[i][x].y), x=par[i][x].x; return rez; } inline int query(int x, int y) { if(depth[y]<depth[x]) swap(x,y); int rez=jump(y,depth[y]-depth[x]); if(x==y) return rez; for(int i=20; i>=0; i--) if(par[i][x].x!=par[i][y].x) { rez=min(rez,min(par[i][x].y,par[i][y].y)); x=par[i][x].x, y=par[i][y].x; } return min(rez, min(par[0][x].y,par[0][y].y)); } signed main() { cin.tie(NULL), cout.tie(NULL); ios_base::sync_with_stdio(false); cin>>n>>m; for(int i=1; i<=n; i++) dp[i]=(1LL<<60), p[i]=-1; while(m--) { cin>>x>>y>>z; e.push_back({x,y,0}); v[x].emplace_back(y,z); v[y].emplace_back(x,z); } cin>>k; while(k--) { cin>>x; dp[x]=0; pq.push({0,x}); } bfs(); build_tree(); precalc(); cin>>q; while(q--) { cin>>x>>y; cout<<query(x,y)<<'\n'; } return 0; }