//#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+k); lca l(n); rep(i, n-1) { int a, b, c; cin >> a >> b >> c; a--; b--; G[a].emplace_back(b, c); G[b].emplace_back(a, c); l.add(a, b, c); } l.init(); vi _(k); rep(i, k) { int m, p; cin >> m >> p; _[i] = p; rep(j, m) { int x; cin >> x; x--; G[x].emplace_back(n+i, p); G[n+i].emplace_back(x, 0); } } PQG> que; vector> dist(k, vector(n+k, LINF)); rep(i, k) { que.emplace(0, n+i); dist[i][n+i] = 0; while(not que.empty()) { auto [d, now] = que.top(); que.pop(); if(dist[i][now] != d) continue; for(auto [to, c]:G[now]) { if(chmin(dist[i][to], d+c)) { que.emplace(d+c, to); } } } } int q; cin >> q; while(q--) { int u, v; cin >> u >> v; u--; v--; ll ans = l.dist(u, v); rep(i, k) chmin(ans, dist[i][u]+dist[i][v]+_[i]); cout << ans << '\n'; } }