class Dijkstra(): class Edge(): def __init__(self, _to, _cost): self.to = _to self.cost = _cost def __init__(self, V): self.G = [[] for i in range(V)] self._E = 0 self._V = V @property def E(self): return self._E @property def V(self): return self._V def add_edge(self, _from, _to, _cost): self.G[_from].append(self.Edge(_to, _cost)) self._E += 1 def shortest_path(self, start): import heapq que = [] d = [10**15] * self.V if type(start)==int: s = start d[s] = 0 heapq.heappush(que, (0, s)) else: for s in start: d[s] = 0 heapq.heappush(que,(0,s)) while len(que) != 0: cost, v = heapq.heappop(que) if d[v] < cost: continue for i in range(len(self.G[v])): e = self.G[v][i] if d[e.to] > d[v] + e.cost: d[e.to] = d[v] + e.cost heapq.heappush(que, (d[e.to], e.to)) return d import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import gcd sys.setrecursionlimit(2*10**5) input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) N,K = mi() edge = [[] for i in range(N)] tree = Dijkstra(N) for _ in range(N-1): a,b,c = mi() edge[a-1].append((b-1,c)) edge[b-1].append((a-1,c)) tree.add_edge(a-1,b-1,c) tree.add_edge(b-1,a-1,c) air = [] air_city = [] for _ in range(K): m,p = mi() air.append((m,p)) air_city.append([int(a)-1 for a in input().split()]) dist_from_air = [[10**17 for i in range(N)] for a in range(K)] for a in range(K): dist_from_air[a] = tree.shortest_path(air_city[a]) airs = Dijkstra(K) for i in range(K): for j in range(K): tmp = 10**17 for _from in air_city[i]: tmp = min(dist_from_air[j][_from],tmp) tmp += air[j][1] airs.add_edge(i,j,tmp) dist = [airs.shortest_path(i) for i in range(K)] # N: 頂点数 # G[v]: 頂点vの子頂点 (親頂点は含まない) parent = [-1 for i in range(N)] deq = deque([0]) while deq: v = deq.popleft() for nv,c in edge[v]: if parent[nv]==-1 and nv!=0: parent[nv] = v deq.append(nv) G = [[(nv,c) for nv,c in edge[v] if nv!=parent[v]] for v in range(N)] # Euler Tour の構築 S = [] F = [0]*N depth = [0]*N depth_dist = [0]*N def dfs(v, d, di): F[v] = len(S) depth[v] = d depth_dist[v] = di S.append(v) for nv,c in G[v]: dfs(nv, d+1, di+c) S.append(v) dfs(0, 0, 0) # 存在しない範囲は深さが他よりも大きくなるようにする INF = (N, None) # LCAを計算するクエリの前計算 M = 2*N M0 = 2**(M-1).bit_length() data = [INF]*(2*M0) for i, v in enumerate(S): data[M0-1+i] = (depth[v], i) for i in range(M0-2, -1, -1): data[i] = min(data[2*i+1], data[2*i+2]) # LCAの計算 (generatorで最小値を求める) def _query(a, b): res = INF a += M0; b += M0 while a < b: if b & 1: b -= 1 res = min(res,data[b-1]) if a & 1: res = min(res,data[a-1]) a += 1 a >>= 1; b >>= 1 return res # LCAの計算 (外から呼び出す関数) def lca(u, v): fu = F[u]; fv = F[v] if fu > fv: fu, fv = fv, fu idx = _query(fu,fv+1) return S[idx[1]] def dist_in_tree(u,v): w = lca(u,v) return depth_dist[u] + depth_dist[v] - 2 * depth_dist[w] ans = [] for _ in range(int(input())): u,v = mi() u,v = u-1,v-1 res = dist_in_tree(u,v) for i in range(K): for j in range(K): tmp = dist_from_air[i][u] + air[i][1] + dist[i][j] + dist_from_air[j][v] res = min(res,tmp) ans.append(res) print(*ans,sep="\n")