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 input = lambda :sys.stdin.buffer.readline() mi = lambda :map(int,input().split()) li = lambda :list(mi()) N,K = mi() edge = [[] for i in range(N)] for _ in range(N-1): a,b,c = mi() edge[a-1].append((b-1,c)) edge[b-1].append((a-1,c)) prv = [-1 for i in range(N)] deq = deque([0]) depth = [0 for i in range(N)] depth_dist = [0 for i in range(N)] res = [] while deq: v = deq.popleft() res.append(v) for nv,c in edge[v]: if prv[nv]==-1 and nv!=0: prv[nv] = v depth_dist[nv] = depth_dist[v] + c depth[nv] = depth[v] + 1 deq.append(nv) res = res[::-1] 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): for city in air_city[a]: dist_from_air[a][city] = 0 for v in res: for nv,c in edge[v]: if nv!=prv[v]: dist_from_air[a][v] = min(dist_from_air[a][v],c+dist_from_air[a][nv]) for v in res[::-1]: for nv,c in edge[v]: if nv!=prv[v]: dist_from_air[a][nv] = min(dist_from_air[a][nv],c+dist_from_air[a][v]) airs = Dijkstra(K) for i in range(K): for j in range(K): tmp = min(dist_from_air[j][_from] for _from in air_city[i]) + air[j][1] airs.add_edge(i,j,tmp) dist = [airs.shortest_path(i) for i in range(K)] # N: 頂点数 # G[v]: 頂点vの子頂点 (親頂点は含まない) # # - construct # prv[u] = v: 頂点uの一つ上の祖先頂点v # - lca # kprv[k][u] = v: 頂点uの2^k個上の祖先頂点v # depth[u]: 頂点uの深さ (根頂点は0) LV = (N-1).bit_length() kprv = [prv] S = prv for k in range(LV): T = [0]*N for i in range(N): if S[i] is None: continue T[i] = S[S[i]] kprv.append(T) S = T def lca(u, v): dd = depth[v] - depth[u] if dd < 0: u, v = v, u dd = -dd # assert depth[u] <= depth[v] for k in range(LV+1): if dd & 1: v = kprv[k][v] dd >>= 1 # assert depth[u] == depth[v] if u == v: return u for k in range(LV-1, -1, -1): pu = kprv[k][u]; pv = kprv[k][v] if pu != pv: u = pu; v = pv # assert kprv[0][u] == kprv[0][v] return kprv[0][u] 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(i,K): tmp_1 = dist_from_air[i][u] + air[i][1] + dist[i][j] + dist_from_air[j][v] tmp_2 = dist_from_air[j][u] + air[i][1] + dist[i][j] + dist_from_air[i][v] res = min(res,tmp_1,tmp_2) ans.append(res) print(*ans,sep="\n")