#include using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { ++itr; } constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator * () const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept: first(first), last(std::max(first, last)) { } constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template constexpr T INFTY = std::numeric_limits::max() / Div; template bool setmin(T& lhs, const T& rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template struct RecLambda: private F { explicit constexpr RecLambda(F&& f): F(std::forward(f)) { } template constexpr decltype(auto) operator () (Args&&... args) const { return F::operator()(*this, std::forward(args)...); } }; class revrep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { --itr; } constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator * () const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr revrep(const usize first, const usize last) noexcept: first(last - 1), last(std::min(first, last) - 1) { } constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template using Vec = std::vector; template using Heap = std::priority_queue, std::greater>; void E_main() { usize N, K; std::cin >> N >> K; Vec>> tree(N), graph(N + K); for (auto i: rep(1, N)) { usize a, b; u32 c; std::cin >> a >> b >> c; a -= 1; b -= 1; tree[a].emplace_back(b, c); tree[b].emplace_back(a, c); graph[a].emplace_back(b, c); graph[b].emplace_back(a, c); } Vec P(K); for (auto i: rep(0, K)) { usize m; std::cin >> m >> P[i]; while (m--) { usize u; std::cin >> u; u -= 1; graph[u].emplace_back(N + i, P[i]); graph[N + i].emplace_back(u, 0); } } const auto dijkstra = [&](const usize src) { Vec dist(N + K, INFTY); Heap> que; const auto push = [&](const usize u, const u64 d) { if (setmin(dist[u], d)) { que.emplace(d, u); } }; push(src, 0); while (!que.empty()) { const auto [d, u] = que.top(); que.pop(); if (dist[u] < d) { continue; } for (const auto [v, c]: graph[u]) { push(v, d + c); } } return dist; }; Vec> dist(K); for (auto i: rep(0, K)) { dist[i] = dijkstra(N + i); } Vec parent(N), depth(N); Vec length(N); RecLambda([&](auto &&dfs, const usize u, const usize p, const usize d, const u64 l) -> void { parent[u] = p; depth[u] = d; length[u] = l; for (const auto [v, c]: tree[u]) { if (v != p) { dfs(v, u, d + 1, l + c); } } })(0, 0, 0, 0); std::array, 17> lift; lift[0] = parent; for (auto i: rep(0, 16)) { lift[i + 1].resize(N); for (auto j: rep(0, N)) { lift[i + 1][j] = lift[i][lift[i][j]]; } } const auto lca = [&](usize u, usize v) { if (depth[u] < depth[v]) { std::swap(u, v); } const auto dif = depth[u] - depth[v]; for (auto i: rep(0, 17)) { if (dif >> i & 1) { u = lift[i][u]; } } if (u == v) { return u; } for (auto i: revrep(0, 17)) { if (lift[i][u] != lift[i][v]) { u = lift[i][u]; v = lift[i][v]; } } return parent[u]; }; usize Q; std::cin >> Q; while (Q--) { usize u, v; std::cin >> u >> v; u -= 1; v -= 1; const auto c = lca(u, v); u64 ans = length[u] + length[v] - 2 * length[c]; for (auto i: rep(0, K)) { setmin(ans, dist[i][u] + dist[i][v] + P[i]); } std::cout << ans << '\n'; } return; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); E_main(); return 0; }