#include "bits/stdc++.h" #define MOD 1000000007 #define rep(i, n) for(ll i=0; i < (n); i++) #define rrep(i, n) for(ll i=(n)-1; i >=0; i--) #define ALL(v) v.begin(),v.end() #define rALL(v) v.rbegin(),v.rend() #define FOR(i, j, k) for(ll i=j;i llvec; typedef vector dvec; typedef pair P; typedef long double ld; struct edge{ll x, c;}; struct dijkstra{ ll N; llvec d; vector> e; dijkstra(ll n){ N = n; //d = llvec(N, 1e18); e = vector>(N); } void add_edge(ll from, ll to, ll cost){ e[from].push_back({to, cost}); } void run(ll start){ priority_queue, greater

> que; que.push({0, start}); d = llvec(N, 1e18); d[start]=0; while(!que.empty()){ P q = que.top();que.pop(); ll dc = q.first; ll x = q.second; if(dc>d[x]){ continue; }else{ for(auto ip: e[x]){ if(d[ip.x]<=d[x]+ip.c){ continue; }else{ d[ip.x]= d[x]+ip.c; que.push({d[ip.x], ip.x}); } } } } } }; /* struct segment_tree{ ll N; llvec v; ll init=5e18;//initial value ll f(ll a, ll b){ //function return min(a, b); } segment_tree(ll n){ N=1; while(N0){ i = (i-1)/2; v[i] = f(v[i*2+1], v[i*2+2]); } } void add(ll i, ll val){ i += N-1; v[i] += val; while(i>0){ i = (i-1)/2; v[i] = f(v[i*2+1], v[i*2+2]); } } ll get(ll L, ll R){// L <= i < R L += N-1; R += N-1; ll vl = init; ll vr = init; while(L struct segtree { public: int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } segtree() : segtree(0) {} segtree(int n) : segtree(std::vector(n, e())) {} segtree(const std::vector& v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; using S = ll; S op(S a, S b){ return min(a, b); } S ed(){ return 1e18; } //segtree sg(vector a) vector s; vector in; vector> e; void dfs(ll from, ll to, ll c){ in[to] = s.size(); s.push_back(c); for(auto ie: e[to]){ if(ie.x==from)continue; dfs(to, ie.x, c+ie.c); s.push_back(c); } return; } /************************************** ** A main function starts from here ** ***************************************/ int main(){ ll N, K; cin >> N >> K; dijkstra dijk(N+K); e = vector>(N); rep(i, N-1){ ll a, b, c; cin >> a >> b >> c; a--;b--; e[a].push_back({b, c}); e[b].push_back({a, c}); dijk.add_edge(a, b, c); dijk.add_edge(b, a, c); } in = llvec(N, 0); dfs(-1, 0, 0); segtree sg(s); llvec p; rep(i, K){ ll M, dd; cin >> M >> dd; rep(j, M){ ll x; cin >> x; x--; dijk.add_edge(N+i, x, dd); dijk.add_edge(x, N+i, 0); } p.push_back(dd); } vector d(K); rep(i, K){ dijk.run(N+i); d[i] = dijk.d; } ll Q; cin >> Q; while(Q--){ ll u, v; cin >> u >> v; u--;v--; ll from = min(in[u], in[v]); ll to = max(in[u], in[v])+1; ll ans = s[in[u]] + s[in[v]] - 2*sg.prod(from, to); rep(i, K){ ans = min(ans, d[i][u] + d[i][v]-p[i]); } cout << ans << endl; } return 0; }