#include using namespace std; using ll = long long int; using ull = unsigned long long int; using P = pair; using P3 = pair; using PP = pair; constexpr int INF32 = 1 << 30; constexpr ll INF64 = 1LL << 62; // constexpr ll MOD = 1000000007; constexpr ll MOD = 998244353; constexpr int di[] = {0, 1, 0, -1}; constexpr int dj[] = {1, 0, -1, 0}; constexpr int di8[] = {0, 1, 1, 1, 0, -1, -1, -1}; constexpr int dj8[] = {1, 1, 0, -1, -1, -1, 0, 1}; constexpr double EPS = 1e-10; const double PI = acos(-1); #define ALL(v) (v).begin(),(v).end() #define REP(i,n) for(int i=0,i_len=n; i bool chmax(T1 &a, T2 b) { if (a bool chmin(T1 &a, T2 b) { if (b struct SegmentTree{ private: using F = std::function; int N; std::vector node; F f; Monoid e; // identity element public: SegmentTree(){} SegmentTree(F f, Monoid e):f(f), e(e){} void init(int sz){ N = 1; while(N < sz) N <<= 1; node.assign(2*N-1, e); } void build(std::vector& v){ int sz = int(v.size()); init(sz); for(int i=0; i=0; i--){ node[i] = f(node[i*2+1], node[i*2+2]); } } void update(int k, Monoid x){ k += N-1; node[k] = x; while(k > 0){ k = (k-1)/2; node[k] = f(node[2*k+1], node[2*k+2]); } } // [a,b) Monoid query(int a, int b){return query(a, b, 0, 0, N);} Monoid query(int a, int b, int k, int l, int r){ if(b <= l || r <= a) return e; if(a <= l && r <= b) return node[k]; Monoid vl, vr; vl = query(a, b, 2*k+1, l, (l+r)/2); vr = query(a, b, 2*k+2, (l+r)/2, r); return f(vl, vr); } }; template struct LCA { using P = std::pair; using CostType = T; const int INF = 1<<30; struct edge { int from, to, rev; CostType cost; edge(int from, int to, int rev, CostType cost) : from(from), to(to), rev(rev), cost(cost){} }; int V = 0; int root = 0; std::vector > graph; std::vector depth, vs, ds, us; // ds[v]:go down to v, us[v]:go up from v private: SegmentTree

rmq = SegmentTree

([](P a, P b){return min(a,b);},P(INF,-1)); SegmentTree rsq = SegmentTree([](CostType a, CostType b){return a+b;}, 0); void dfs(int v, int p, int d, int &idx){ vs[idx] = v; depth[v] = d; ds[v] = idx++; for(auto& e : graph[v]){ if(e.to == p) continue; dfs(e.to, v, d+1, idx); vs[idx] = v; idx++; } us[v] = idx; } public: LCA() = default; LCA(int V, int root = 0) : V(V), graph(V), depth(V), vs(V*2-1), ds(V), us(V), root(root){} void init(int n, int r = 0){ V = n; graph.resize(V); depth.resize(V); vs.resize(V*2-1); ds.resize(V); us.resize(V); root = r; } void add_edge(int from, int to, CostType cost = 1){ graph[from].emplace_back(edge(from,to,int(graph[to].size()),cost)); graph[to].emplace_back(edge(to,from,int(graph[from].size())-1,cost)); } void build(){ int idx = 0; dfs(root, -1, 0, idx); std::vector

depv(idx); for(int i=0;i cstv(idx, 0); for(int i=0;i> N >> K; LCA lca(N); REP(i,N-1){ ll a, b, c; cin >> a >> b >> c; a--;b--; lca.add_edge(a,b,c); } lca.build(); vector p(K); vector > ardt(K,vector(N,INF64)), a2a(K,vector(K,INF64)); REP(i,K){ int m; cin >> m >> p[i]; queue > que; REP(j,m){ int x; cin >> x; x--; que.push(make_pair(x,0)); ardt[i][x] = 0; } while(!que.empty()){ auto p = que.front(); que.pop(); int now = p.first; if(ardt[i][now] < p.second) continue; for(auto e : lca.graph[now]){ if(chmin(ardt[i][e.to], ardt[i][now]+e.cost)){ que.push(make_pair(e.to,ardt[i][e.to])); } } } } REP(i,K) REP(j,K) REP(k,N) chmin(a2a[i][j], ardt[i][k]+ardt[j][k]); REP(k,K) REP(i,K) REP(j,K){ chmin(a2a[i][j], a2a[i][k]+a2a[k][j]); } int Q; cin >> Q; REP(i,Q){ int u, v; cin >> u >> v; u--; v--; ll res = lca.dist(u,v); REP(j,K) REP(k,K){ chmin(res, ardt[j][u]+a2a[j][k]+ardt[k][v]+p[j]+(j==k?0:p[k])); } cout << res << endl; } return 0; } int main(){ cin.tie(0); ios::sync_with_stdio(0); cout<> t; for(int i=0;i