#include using namespace std; #define repd(i,a,b) for (ll i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define all(x) (x).begin(),(x).end() template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; typedef pair P; typedef vector vec; using Graph = vector>; const long long INF = 1LL<<60; const long long MOD = 1000000007; // Lowest Common Ancestor by binary lifting // https://youtu.be/8uowVvQ_-Mo?t=4306 template // T: type of cost struct lca { int n, root, l; vector> to; vector> co; vector dep; vector costs; vector> par; lca(int n):n(n),to(n),co(n),dep(n),costs(n) { l = 0; while ((1<>(n+1,vector(l,n)); } void addEdge(int a, int b, T c=0) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void dfs(int v, int d=0, T c=0, int p=-1) { if (p != -1) par[v][0] = p; dep[v] = d; costs[v] = c; for (int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if (u == p) continue; dfs(u, d+1, c+co[v][i], v); } } void init(int _root=0) { root = _root; dfs(root); for (int i = 0; i < l-1; ++i) { for (int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } // LCA int LCA(int a, int b) { if (dep[a] > dep[b]) swap(a,b); int gap = dep[b]-dep[a]; for (int i = l-1; i >= 0; --i) { int len = 1<= len) { gap -= len; b = par[b][i]; } } if (a == b) return a; for (int i = l-1; i >= 0; --i) { int na = par[a][i]; int nb = par[b][i]; if (na != nb) a = na, b = nb; } return par[a][0]; } int length(int a, int b) { int c = LCA(a,b); return dep[a]+dep[b]-dep[c]*2; } T dist(int a, int b) { int c = LCA(a,b); return costs[a]+costs[b]-costs[c]*2; } }; struct edge { ll to, cost; }; //辺 int V; //頂点数 const int MAX_V = 200000; vector> G(MAX_V); ll d[MAX_V]; ll memo[10][MAX_V]; void dijkstra(int s) { //greater

でfirstが小さい順に取り出せる //first:最短距離,second:頂点番号 priority_queue, greater

> que; fill(d, d + V, INF); d[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first)continue; rep(i, G[v].size()) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); ll n,k; cin>>n>>k; lca lca(n); rep(i,n-1){ ll a,b,c; cin>>a>>b>>c; a--;b--; G[a].push_back((edge){b,c}); G[b].push_back((edge){a,c}); lca.addEdge(a,b,c); } lca.init(); V=n+k; vec ps(k); rep(i,k){ ll m,p; cin>>m>>p; ps[i]=p; rep(j,m){ ll x;cin>>x; x--; G[x].push_back((edge){i+n,p}); G[i+n].push_back((edge){x,0}); } } rep(i,k){ dijkstra(i+n); swap(d,memo[i]); } ll q;cin>>q; rep(qi,q){ ll a,b; cin>>a>>b; a--;b--; ll ans=lca.dist(a,b); rep(i,k){ ll now=ps[i]+memo[i][a]+memo[i][b]; chmin(ans,now); } cout<