#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <map> using namespace std; vector<pair<int,int> > edge[110000]; int par[110000],distD[110000],distN[110000],howmany[110000]; int cnt[110000]; int todos[110000]; int *todo[110000]; int ntodo[110000]; int N,T,K; void dists(int rt, int pt, int d, int n) { par[rt]=pt; distN[rt]=n; distD[rt]=d; //cout << rt << " " << pt << " " << d << endl; for(auto& p: edge[rt]) if(p.first!=pt) { dists(p.first, rt, p.second, n+1); } } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ cin >> N >> T; for(int n=0; n<N-1; n++) { int A,B,C; scanf("%d %d %d",&A,&B,&C); edge[A-1].push_back(make_pair(B-1,C)); edge[B-1].push_back(make_pair(A-1,C)); } dists(0,-1,0,0); for(int i=0; i<N; i++) howmany[i]=0; for(int i=0; i<N; i++) howmany[distN[i]]++; todo[0]=&todos[0]; for(int i=1; i<N; i++) todo[i] = todo[i-1] + howmany[i-1]; for(int t=0; t<T; t++) { //cout << t<<"/"<<T << endl; cin >> K; int x; map<int,int> se; for(int k=0; k<K; k++) { scanf("%d",&x); cnt[x-1]++; se[x-1]++; } int maxi=0; for(auto p: se) { int x = distN[p.first]; todo[x][ntodo[x]++] = p.first; maxi=max(maxi,x); } se.clear(); long ret=0; for(int i=maxi; i>=0; i--) { if(ntodo[i] && cnt[todo[i][0]]==K) { cnt[todo[i][0]]=0; ntodo[i]=0; break; } for(int* pj=todo[i]; pj<todo[i]+ntodo[i]; pj++) { int j=*pj; if(cnt[j]) { ret += cnt[j] * 1L * distD[j] * (K-cnt[j]); //cout << "Moving " << cnt[j] << " from " << j+1 << " to " << par[j]+1 << " each at cost " << (dist[j]-dist[par[j]]) << " (i=" << T-1 << ")" << endl; if(cnt[par[j]]==0) todo[i-1][ntodo[i-1]++]=par[j]; cnt[par[j]] += cnt[j]; cnt[j]=0; } } ntodo[i]=0; } cout << ret << endl; } return 0; }