//#define _GLIBCXX_DEBUG #include using namespace std; #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater>; const int INF = 0xccccccc; const ll LINF = 0xcccccccccccccccLL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} template struct lca { int n, root, l; vector > to, par; vector > co; vector dep; vector costs; lca(int n):n(n), to(n), co(n), dep(n), costs(n) { l = 0; while((1< >(n+1, vector(l, n)); } void add(int a, int b, T c=0) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void dfs(int v, int d=0, T c=0, int p=-1) { if(p != -1) par[v][0] = p; dep[v] = d; costs[v] = c; for(int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if(u == p) continue; dfs(u, d+1, c+co[v][i], v); } } void init(int _root=0) { root = _root; dfs(root); for(int i = 0; i < l-1; ++i) { for(int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } int lca_(int a, int b) { if(dep[a] > dep[b]) swap(a, b); int gap = dep[b]-dep[a]; for(int i = l-1; i >= 0; --i) { int len = 1<= len) { gap -= len; b = par[b][i]; } } if(a == b) return a; for(int i = l-1; i >= 0; --i) { int na = par[a][i]; int nb = par[b][i]; if(na != nb) { a = na; b = nb; } } return par[a][0]; } int length(int a, int b) { int c = lca_(a, b); return dep[a]+dep[b]-dep[c]*2; } T dist(int a, int b) { int c = lca_(a, b); return costs[a]+costs[b]-costs[c]*2; } }; //head int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector>> G(n); lca l(n); rep(i, n-1) { int a, b, c; cin >> a >> b >> c; a--; b--; l.add(a, b, c); G[a].emplace_back(b, c); G[b].emplace_back(a, c); } l.init(); vi m(k), p(k); vvi x(k); vvi mg(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]--; } sort(all(x[i])); rep(j, i) { int k = 0; for(auto z:x[i]) { while(k < m[j] and x[j][k] < z) k++; if(x[j][k] == z) { mg[i].emplace_back(j); mg[j].emplace_back(i); break; } } } } vector> dist(1<(n, LINF)); vector su(1<> q; for(int i = 1; i < 1<>j&1) lst.emplace_back(j); int siz = size(lst); vi cnt(siz); rep(j, siz) { int x = 0; for(auto ne:mg[lst[j]]) { while(x < siz and lst[x] < ne) x++; if(lst[x] == ne) cnt[ne]++; } } rep(j, siz) if(cnt[j] <= 1) { u = lst[j]; break; } ll mi = LINF; rep(j, m[u]) chmin(mi, dist[i^(1<> qq; while(qq--) { int u, v; cin >> u >> v; u--; v--; ll ans = l.dist(u, v); for(int i = 1; i < 1<