#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define reps(x, s) for(llint (x) = 0; (x) < (llint)(s).size(); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define sz(x) ((ll)(x).size()) #define ceil(x, y) (((x)+(y)-1) / (y)) #define all(x) (x).begin(),(x).end() #define outl(...) dump_func(__VA_ARGS__) #define inf 1e18 using namespace std; typedef long long llint; typedef long long ll; typedef pair P; struct edge{ ll to, cost; edge(){} edge(ll a, ll b){ to = a, cost = b;} }; const ll mod = 1000000007; const ll mod2 = 998244353; struct mint{ ll x = 0; mint(ll y = 0){x = y; if(x < 0 || x >= mod) x = (x%mod+mod)%mod;} mint(const mint &ope) {x = ope.x;} mint operator-(){return mint(-x);} mint operator+(const mint &ope){return mint(x) += ope;} mint operator-(const mint &ope){return mint(x) -= ope;} mint operator*(const mint &ope){return mint(x) *= ope;} mint operator/(const mint &ope){return mint(x) /= ope;} mint& operator+=(const mint &ope){ x += ope.x; if(x >= mod) x -= mod; return *this; } mint& operator-=(const mint &ope){ x += mod - ope.x; if(x >= mod) x -= mod; return *this; } mint& operator*=(const mint &ope){ x *= ope.x, x %= mod; return *this; } mint& operator/=(const mint &ope){ ll n = mod-2; mint mul = ope; while(n){ if(n & 1) *this *= mul; mul *= mul; n >>= 1; } return *this; } mint inverse(){return mint(1) / *this;} bool operator ==(const mint &ope){return x == ope.x;} bool operator !=(const mint &ope){return x != ope.x;} }; mint modpow(mint a, ll n){ if(n == 0) return mint(1); if(n % 2) return a * modpow(a, n-1); else return modpow(a*a, n/2); } istream& operator >>(istream &is, mint &ope){ ll t; is >> t, ope.x = t; return is; } ostream& operator <<(ostream &os, mint &ope){return os << ope.x;} ostream& operator <<(ostream &os, const mint &ope){return os << ope.x;} bool exceed(ll x, ll y, ll m){return x >= m / y + 1;} void mark(){ cout << "*" << endl; } void yes(){ cout << "Yes" << endl; } void no(){ cout << "No" << endl; } ll gcd(ll a, ll b){if(b == 0) return a; return gcd(b, a%b);} template ostream& operator << (ostream& os, vector& vec) { for(int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : " "); } return os; } template ostream& operator << (ostream& os, deque& deq) { for(int i = 0; i < deq.size(); i++) { os << deq[i] << (i + 1 == deq.size() ? "" : " "); } return os; } template ostream& operator << (ostream& os, pair& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } template ostream& operator << (ostream& os, const pair& pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } template ostream& operator << (ostream& os, map& map_var) { for(typename map::iterator itr = map_var.begin(); itr != map_var.end(); itr++) { os << "(" << itr->first << ", " << itr->second << ")"; itr++; if(itr != map_var.end()) os << ","; itr--; } return os; } template ostream& operator << (ostream& os, set& set_var) { for(typename set::iterator itr = set_var.begin(); itr != set_var.end(); itr++) { os << *itr; ++itr; if(itr != set_var.end()) os << " "; itr--; } return os; } template void outa(T a[], ll s, ll t) { for(ll i = s; i <= t; i++){ cout << a[i]; if(i < t) cout << " ";} cout << endl; } void dump_func() {cout << endl;} template void dump_func(Head &&head, Tail &&... tail) { cout << head; if(sizeof...(Tail) > 0) cout << " "; dump_func(std::move(tail)...); } ll n, k, Q; vector G[100005]; ll p[15]; vector vec[15]; ll dist[15][100005]; ll g[15][15]; void dijkstra(vector G[], ll id, llint dist[]) { for(int i = 1; i <= n; i++) dist[i] = inf; priority_queue< P, vector

, greater

> Q; for(auto v : vec[id]){ Q.push( make_pair(0, v) ); dist[v] = 0; } llint v, d; while(Q.size()){ d = Q.top().first; v = Q.top().second; Q.pop(); if(dist[v] < d) continue; for(int i = 0; i < G[v].size(); i++){ if(dist[G[v][i].to] > d + G[v][i].cost){ dist[G[v][i].to] = d + G[v][i].cost; Q.push( make_pair(dist[G[v][i].to], G[v][i].to) ); } } } } const int VNUM = 200005, LOG_VNUM = 18; int Prev[VNUM][LOG_VNUM]; int depth[VNUM]; ll length[VNUM]; void predfs(int v, int p, int d, ll l) { depth[v] = d, Prev[v][0] = p, length[v] = l; for(int i = 0; i < G[v].size(); i++){ if(G[v][i].to == p) continue; predfs(G[v][i].to, v, d+1, G[v][i].cost + l); } } int getLCA(int u, int v){ int x = u, y = v; if(depth[y] > depth[x]) swap(x, y); for(int i = LOG_VNUM-1; i >= 0; i--){ if(depth[x] - (1<= depth[y]) x = Prev[x][i]; } if(x == y) return x; for(int i = LOG_VNUM-1; i >= 0; i--){ if(Prev[x][i] != Prev[y][i]){ x = Prev[x][i]; y = Prev[y][i]; } } x = Prev[x][0]; return x; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; ll u, v, w; rep(i, 1, n-1){ cin >> u >> v >> w; G[u].push_back(edge(v, w)); G[v].push_back(edge(u, w)); } ll m, x; rep(i, 1, k){ cin >> m >> p[i]; rep(j, 1, m){ cin >> x; vec[i].push_back(x); } } rep(i, 1, k) dijkstra(G, i, dist[i]); rep(i, 1, k) rep(j, 1, k){ g[i][j] = inf; for(auto v : vec[j]) chmin(g[i][j], dist[i][v]); g[i][j] += p[j]; if(i == j) g[i][j] = 0; } rep(z, 1, k) rep(i, 1, k) rep(j, 1, k) chmin(g[i][j], g[i][z] + g[z][j]); predfs(1, 0, 0, 0); for(int i = 1; i < LOG_VNUM; i++){ for(int j = 1; j <= n; j++){ Prev[j][i] = Prev[Prev[j][i-1]][i-1]; } } cin >> Q; rep(q, 1, Q){ cin >> u >> v; ll ans = length[u] + length[v] - 2 * length[getLCA(u, v)]; rep(i, 1, k) rep(j, 1, k){ chmin(ans, dist[i][u] + p[i] + g[i][j] + dist[j][v]); } cout << ans << "\n"; } flush(cout); return 0; }