#include using namespace std; typedef long long ll; const ll INF = 1e18; struct LCA { vector depth; vector> parent; vector> dist; int max_log; LCA(int n, const vector>> &tree) { max_log = 0; while ((1 << max_log) < n) max_log++; depth.resize(n); parent.assign(max_log, vector(n, -1)); dist.assign(max_log, vector(n, 0)); queue q; q.push(0); depth[0] = 0; parent[0][0] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (auto &[v, c] : tree[u]) { if (parent[0][v] == -1 && v != 0) { depth[v] = depth[u] + 1; parent[0][v] = u; dist[0][v] = c; q.push(v); } } } for (int k = 1; k < max_log; k++) { for (int v = 0; v < n; v++) { if (parent[k-1][v] != -1) { parent[k][v] = parent[k-1][parent[k-1][v]]; dist[k][v] = dist[k-1][v] + dist[k-1][parent[k-1][v]]; } } } } pair lca(int u, int v) { ll sum = 0; if (depth[u] < depth[v]) swap(u, v); for (int k = max_log-1; k >= 0; k--) { if (depth[u] - (1 << k) >= depth[v]) { sum += dist[k][u]; u = parent[k][u]; } } if (u == v) return {u, sum}; for (int k = max_log-1; k >= 0; k--) { if (parent[k][u] != -1 && parent[k][u] != parent[k][v]) { sum += dist[k][u] + dist[k][v]; u = parent[k][u]; v = parent[k][v]; } } sum += dist[0][u] + dist[0][v]; return {parent[0][u], sum}; } ll distance(int u, int v) { auto [ancestor, d] = lca(u, v); return d; } }; vector dijkstra_airline(const vector>> &tree, const vector &sources) { int n = tree.size(); vector dist(n, INF); priority_queue, vector>, greater>> pq; for (int s : sources) { dist[s] = 0; pq.emplace(0, s); } while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto [v, c] : tree[u]) { if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; pq.emplace(dist[v], v); } } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector>> tree(N); for (int i = 0; i < N-1; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; tree[a].emplace_back(b, c); tree[b].emplace_back(a, c); } LCA lca(N, tree); vector P(K); vector> min_dist(K); for (int i = 0; i < K; i++) { int M, p; cin >> M >> p; P[i] = p; vector sources; for (int j = 0; j < M; j++) { int x; cin >> x; x--; sources.push_back(x); } min_dist[i] = dijkstra_airline(tree, sources); } vector sum_P(1 << K, 0); for (int mask = 1; mask < (1 << K); mask++) { for (int i = 0; i < K; i++) { if (mask & (1 << i)) { sum_P[mask] = sum_P[mask ^ (1 << i)] + P[i]; break; } } } int Q; cin >> Q; vector sorted_a_order(K), sorted_b_order(K); while (Q--) { int u, v; cin >> u >> v; u--; v--; ll rail_cost = lca.distance(u, v); if (K == 0) { cout << rail_cost << '\n'; continue; } vector a(K), b(K); for (int i = 0; i < K; i++) { a[i] = min_dist[i][u]; b[i] = min_dist[i][v]; } iota(sorted_a_order.begin(), sorted_a_order.end(), 0); sort(sorted_a_order.begin(), sorted_a_order.end(), [&a](int i, int j) { return a[i] < a[j]; }); iota(sorted_b_order.begin(), sorted_b_order.end(), 0); sort(sorted_b_order.begin(), sorted_b_order.end(), [&b](int i, int j) { return b[i] < b[j]; }); ll min_candidate = INF; for (int mask = 1; mask < (1 << K); mask++) { ll sum_p = sum_P[mask]; ll current_a = INF; for (int i : sorted_a_order) { if (mask & (1 << i)) { current_a = a[i]; break; } } ll current_b = INF; for (int i : sorted_b_order) { if (mask & (1 << i)) { current_b = b[i]; break; } } if (current_a == INF || current_b == INF) continue; ll candidate = sum_p + current_a + current_b; if (candidate < min_candidate) { min_candidate = candidate; } } ll answer = min(rail_cost, min_candidate); cout << answer << '\n'; } return 0; }