#include #include #include using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000000000000 vector>> E; vector get(vector ind){ priority_queue,vector>,greater>> Q; vector dis(E.size(),Inf); rep(i,ind.size()){ Q.emplace(0,ind[i]); dis[ind[i]] = 0; } while(Q.size()>0){ long long D = Q.top().first; int u = Q.top().second; Q.pop(); if(dis[u]!=D)continue; rep(i,E[u].size()){ long long D2 = E[u][i].second; int v = E[u][i].first; if(dis[v]<=D+D2)continue; dis[v] = D+D2; Q.emplace(dis[v],v); } } return dis; } struct HLD{ vector sz,parent,depth,root,pos; vector arr; HLD(vector> &E){ sz.resize(E.size(),1); parent.resize(E.size(),0); depth.resize(E.size(),0); root.resize(E.size(),0); pos.resize(E.size(),0); dfs(0,-1,E); dfs2(0,-1,E,0); } void dfs(int now,int p,vector> &E){ parent[now] = p; if(p==-1){ depth[now] = 0; } else{ depth[now] = depth[p]+1; } for(int i=0;i> &E,int r){ pos[now] = arr.size(); arr.push_back(now); root[now] = r; int maxi = 0; int ind = -1; for(int i=0;i> query(int u,int v){ vector> ret; int t = 0; while(root[u]!=root[v]){ if(depth[root[u]] <= depth[root[v]]){ ret.insert(ret.begin()+t,{pos[root[v]], pos[v]}); v = parent[root[v]]; } else{ ret.insert(ret.begin()+t,{pos[u],pos[root[u]]}); u = parent[root[u]]; t++; } } ret.insert(ret.begin()+t,{pos[u],pos[v]}); return ret; } int lca(int u,int v){ for(;;v=parent[root[v]]){ if(pos[u]>pos[v])swap(u,v); if(root[u]==root[v])return u; } } int get_distance(int u,int v){ return depth[u] + depth[v] - 2 * depth[lca(u,v)]; } }; int main(){ int N,K; cin>>N>>K; vector> e(N); E.resize(N); rep(i,N-1){ int a,b,c; scanf("%d %d %d",&a,&b,&c); a--;b--; E[a].emplace_back(b,c); E[b].emplace_back(a,c); e[a].push_back(b); e[b].push_back(a); } vector M(K); vector P(K); vector> X(K); rep(i,K){ scanf("%d %lld",&M[i],&P[i]); X[i].resize(M[i]); rep(j,M[i]){ scanf("%d",&X[i][j]); X[i][j]--; } } //cout<<'a'<> dis(K); rep(i,K){ dis[i] = get(X[i]); } //cout<<'a'<(K*2,Inf)); rep(i,K*2)d[i][i] = 0LL; //cout<<'a'< D(N,Inf); D[0] = 0; { queue Q; Q.push(0); while(Q.size()>0){ int u = Q.front(); Q.pop(); rep(i,E[u].size()){ int v = E[u][i].first; long long dd = E[u][i].second; if(D[v]==Inf){ D[v] = D[u]+dd; Q.push(v); } } } } //cout<<'a'<>Q; rep(_,Q){ int u,v; scanf("%d %d",&u,&v); u--;v--; long long ans = D[u] + D[v] - D[H.lca(u,v)]*2; rep(i,K){ rep(j,K){ ans = min(ans,dis[i][u] + d[i*2][j*2+1] + dis[j][v]); } } printf("%lld\n",ans); } return 0; }