#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a> g; int root; vector parent[MAX_LOG_V]; vector depth; LowestCommonAncestor(){} LowestCommonAncestor(int V,int root_):g(V),depth(V){ root=root_; for(int i=0;idepth[v]) swap(u,v); for(int k=0;k>k&1){ v=parent[k][v]; } } if(u==v) return u; for(int k=MAX_LOG_V-1;k>=0;k--){ if(parent[k][u]!=parent[k][v]){ u=parent[k][u]; v=parent[k][v]; } } return parent[0][u]; } }; struct Edge{ int to; ll cost; Edge(){} Edge(int to,ll cost):to(to),cost(cost){} }; const ll INF=1e18; vector dijkstra(int st,vector> &g){ int N=g.size(); vector dist(N,INF); dist[st]=0; priority_queue,vector>,greater>> PQ; PQ.push(mkp(0,st)); while(!PQ.empty()){ auto [d,now]=PQ.top(); PQ.pop(); if(dist[now]dist[now]+e.cost){ dist[e.to]=dist[now]+e.cost; PQ.push(mkp(dist[e.to],e.to)); } } } return dist; } int main(){ cin.tie(0); ios::sync_with_stdio(false); int N,K; cin>>N>>K; vector> g(N+K); vector> tree(N); LowestCommonAncestor lca(N,0); rep(i,N-1){ int a,b; ll c; cin>>a>>b>>c; a--;b--; g[a].push_back({b,c}); g[b].push_back({a,c}); tree[a].push_back({b,c}); tree[b].push_back({a,c}); lca.add_edge(a,b); } lca.build(N); vector M(K); vector P(K); vector> X(K); rep(i,K){ cin>>M[i]>>P[i]; X[i].resize(M[i]); rep(j,M[i]){ cin>>X[i][j]; X[i][j]--; } } rep(i,K){ rep(j,M[i]){ g[N+i].push_back({X[i][j],0}); g[X[i][j]].push_back({N+i,P[i]}); } } vector> dist(K); rep(i,K) dist[i]=dijkstra(N+i,g); vector tree_dist(N); {// tree auto dfs = [&](auto &&dfs,int now,int par,ll d)->void{ tree_dist[now]=d; for(auto e:tree[now]){ if(e.to==par) continue; dfs(dfs,e.to,now,d+e.cost); } }; dfs(dfs,0,-1,0); } int Q; cin>>Q; rep(q,Q){ int a,b; cin>>a>>b; a--;b--; ll ans=INF; int l=lca.query(a,b); chmin(ans,tree_dist[a]+tree_dist[b]-2*tree_dist[l]); rep(k,K) chmin(ans,dist[k][a]+dist[k][b]+P[k]); cout<