#include using namespace std; using Int = long long; const char newl = '\n'; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a void drop(const T &x){cout< vector read(size_t n){ vector ts(n); for(size_t i=0;i>ts[i]; return ts; } template struct Dijkstra{ struct Edge{ Int to; T cost; Edge(Int to,T cost):to(to),cost(cost){} bool operator<(const Edge &o)const{return cost>o.cost;} }; vector< vector > G; vector ds; vector bs; Dijkstra(Int n):G(n){} void add_edge(Int u,Int v,T c){ G[u].emplace_back(v,c); } void build(Int s){ Int n=G.size(); ds.assign(n,numeric_limits::max()); bs.assign(n,-1); priority_queue pq; ds[s]=0; pq.emplace(s,ds[s]); while(!pq.empty()){ auto p=pq.top();pq.pop(); Int v=p.to; if(ds[v]ds[v]+e.cost){ ds[e.to]=ds[v]+e.cost; bs[e.to]=v; pq.emplace(e.to,ds[e.to]); } } } } T operator[](Int k){return ds[k];} vector restore(Int to){ vector res; if(bs[to]<0) return res; while(~to) res.emplace_back(to),to=bs[to]; reverse(res.begin(),res.end()); return res; } }; struct LowestCommonAncestor{ Int h; vector< vector > G,par; vector dep; LowestCommonAncestor(Int n):G(n),dep(n){ h=1; while((1<(n,-1)); } void add_edge(Int u,Int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void dfs(Int v,Int p,Int d){ par[0][v]=p; dep[v]=d; for(Int u:G[v]) if(u!=p) dfs(u,v,d+1); } void build(Int r=0){ Int n=G.size(); dfs(r,-1,0); for(Int k=0;k+1dep[v]) swap(u,v); for(Int k=0;k>k&1) v=par[k][v]; if(u==v) return u; for(Int k=h-1;k>=0;k--) if(par[k][u]!=par[k][v]) u=par[k][u],v=par[k][v]; return par[0][u]; } Int distance(Int u,Int v){ return dep[u]+dep[v]-dep[lca(u,v)]*2; } }; template struct FixPoint : F{ FixPoint(F&& f):F(forward(f)){} template decltype(auto) operator()(Args&&... args) const{ return F::operator()(*this,forward(args)...); } }; template inline decltype(auto) MFP(F&& f){ return FixPoint{forward(f)}; } //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); Int n,k; cin>>n>>k; using P = pair; vector> G(n); Dijkstra D(n+k); LowestCommonAncestor lca(n); for(Int i=1;i>a>>b>>c; a--;b--; G[a].emplace_back(b,c); G[b].emplace_back(a,c); D.add_edge(a,b,c); D.add_edge(b,a,c); lca.add_edge(a,b); } lca.build(0); vector dep(n); MFP([&](auto dfs,Int v,Int p,Int d)->void{ dep[v]=d; for(auto[u,c]:G[v]) if(u!=p) dfs(u,v,d+c); })(0,-1,0); vector> X(k),C(n); vector ps(k); for(Int i=0;i>m>>ps[i]; X[i].resize(m); for(Int j=0;j>X[i][j],X[i][j]--; C[X[i][j]].emplace_back(i); D.add_edge(X[i][j],n+i,ps[i]); D.add_edge(n+i,X[i][j],0); } } const Int INF = 1e18; vector> E,dist; for(Int i=0;i>q; for(Int i=0;i>u>>v; u--;v--; Int ans=dep[u]+dep[v]-2*dep[lca.lca(u,v)]; for(Int x=0;x