#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template struct Edge { int src, dst; CostType cost; Edge(int src, int dst, CostType cost = 0) : src(src), dst(dst), cost(cost) {} inline bool operator<(const Edge &x) const { return cost != x.cost ? cost < x.cost : dst != x.dst ? dst < x.dst : src < x.src; } inline bool operator<=(const Edge &x) const { return !(x < *this); } inline bool operator>(const Edge &x) const { return x < *this; } inline bool operator>=(const Edge &x) const { return !(*this < x); } }; template struct LCADoubling { std::vector depth; std::vector dist; LCADoubling(const std::vector>> &graph) : graph(graph) { n = graph.size(); depth.resize(n); dist.resize(n); while ((1 << table_h) <= n) ++table_h; parent.resize(table_h, std::vector(n)); } void build(int root = 0) { is_built = true; dfs(-1, root, 0, 0); for (int i = 0; i + 1 < table_h; ++i) for (int ver = 0; ver < n; ++ver) { parent[i + 1][ver] = parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]; } } int query(int u, int v) const { assert(is_built); if (depth[u] > depth[v]) std::swap(u, v); for (int i = 0; i < table_h; ++i) { if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v]; } if (u == v) return u; for (int i = table_h - 1; i >= 0; --i) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } CostType distance(int u, int v) const { assert(is_built); return dist[u] + dist[v] - dist[query(u, v)] * 2; } private: bool is_built = false; int n, table_h = 1; std::vector>> graph; std::vector> parent; void dfs(int par, int ver, int now_depth, CostType now_dist) { depth[ver] = now_depth; dist[ver] = now_dist; parent[0][ver] = par; for (const Edge &e : graph[ver]) { if (e.dst != par) dfs(ver, e.dst, now_depth + 1, now_dist + e.cost); } } }; template struct WarshallFloyd { std::vector> graph, dist; WarshallFloyd(const std::vector> &graph, const T inf) : graph(graph), dist(graph), inf(inf) { n = graph.size(); internal.assign(n, std::vector(n, -1)); for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; internal[i][j] = k; } } } void add(int src, int dst, T cost) { srcs.emplace_back(src); dsts.emplace_back(dst); costs.emplace_back(cost); } void calc() { std::set vers; int sz = srcs.size(); for (int i = 0; i < sz; ++i) { int s = srcs[i], t = dsts[i]; T cost = costs[i]; if (cost < graph[s][t]) graph[s][t] = cost; if (dist[s][t] >= cost) { dist[s][t] = cost; internal[s][t] = -1; } vers.emplace(s); vers.emplace(t); } for (int v : vers) { for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (dist[i][j] > dist[i][v] + dist[v][j]) { dist[i][j] = dist[i][v] + dist[v][j]; internal[i][j] = v; } } } srcs.clear(); dsts.clear(); costs.clear(); } bool has_negative_cycle() const { for (int i = 0; i < n; ++i) { if (dist[i][i] < 0) return true; } return false; } std::vector build_path(int s, int t) const { std::vector res; if (dist[s][t] != inf) { build_path(s, t, res); res.emplace_back(t); } return res; } private: const T inf; int n; std::vector> internal; std::vector srcs, dsts; std::vector costs; void build_path(int s, int t, std::vector &path) const { int k = internal[s][t]; if (k == -1) { path.emplace_back(s); } else { build_path(s, k, path); build_path(k, t, path); } } }; int main() { int n, k; cin >> n >> k; vector>> graph(n); REP(_, n - 1) { int a, b, c; cin >> a >> b >> c; --a; --b; graph[a].emplace_back(a, b, c); graph[b].emplace_back(b, a, c); } LCADoubling lca(graph); lca.build(); vector p(k); vector> x(k); REP(i, k) { int m; cin >> m >> p[i]; x[i].resize(m); REP(j, m) cin >> x[i][j], --x[i][j]; } vector dist(k, vector(n, LINF)); REP(i, k) { priority_queue, vector>, greater>> que; REP(j, x[i].size()) { dist[i][x[i][j]] = 0; que.emplace(0, x[i][j]); } while (!que.empty()) { auto [cost, city] = que.top(); que.pop(); if (cost > dist[i][city]) continue; for (const Edge &e : graph[city]) { if (ll nx = dist[i][city] + e.cost; nx < dist[i][e.dst]) { dist[i][e.dst] = nx; que.emplace(nx, e.dst); } } } } vector g(k, vector(k, LINF)); REP(i, k) REP(j, k) for (int e : x[j]) chmin(g[i][j], dist[i][e]); WarshallFloyd wf(g, LINF); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; --u; --v; ll ans = lca.distance(u, v); vector d(k, LINF); priority_queue, vector>, greater>> que; REP(i, k) { d[i] = dist[i][u] + p[i]; que.emplace(d[i], i); } while (!que.empty()) { auto [cost, airport] = que.top(); que.pop(); if (cost > d[airport]) continue; REP(i, k) { if (ll nx = d[airport] + g[airport][i] + p[i]; nx < d[i]) { d[i] = nx; que.emplace(nx, i); } } } REP(i, k) chmin(ans, d[i] + dist[i][v]); cout << ans << '\n'; } return 0; }