import sys readline=sys.stdin.readline import heapq class Path_Doubling: def __init__(self,N,permutation,lst=None,f=None,e=None): self.N=N self.permutation=permutation self.lst=lst self.f=f self.e=e def Build_Next(self,K=None): if K==None: K=self.N self.k=K.bit_length() self.permutation_doubling=[[None]*self.N for k in range(self.k)] for n in range(self.N): self.permutation_doubling[0][n]=self.permutation[n] if self.lst!=None: self.doubling=[[None]*self.N for k in range(self.k)] for n in range(self.N): self.doubling[0][n]=self.lst[n] for k in range(1,self.k): for n in range(self.N): if self.permutation_doubling[k-1][n]!=None: self.permutation_doubling[k][n]=self.permutation_doubling[k-1][self.permutation_doubling[k-1][n]] if self.f!=None: self.doubling[k][n]=self.f(self.doubling[n][k-1],self.doubling[k-1][self.permutation_doubling[k-1][n]]) def Permutation_Doubling(self,N,K): if K<0 or 1<>k&1 and N!=None: N=self.permutation_doubling[k][N] return N def Doubling(self,N,K): if K<0: return self.e retu=self.e for k in range(self.k): if K>>k&1: if self.permutation_doubling[k][N]==None: return None retu=self.f(retu,self.doubling[k][N]) N=self.permutation_doubling[k][N] return N,retu def Bisect(self,x,is_ok): if not is_ok(x): return -1,None K=0 for k in range(self.k-1,-1,-1): if is_ok(self.permutation_doubling[k][x]): K|=1<=0: self.lca_dfs_in_index[x]=i else: self.lca_dfs_out_index[~x]=i self.ST=Segment_Tree(2*self.V,lambda x,y:min(x,y),self.V) lst=[None]*(2*self.V) for i in range(2*self.V-1): if self.lca_euler_tour[i]>=0: lst[i]=depth[self.lca_euler_tour[i]] else: lst[i]=depth[self.lca_parents[~self.lca_euler_tour[i]]] lst[2*self.V-1]=-1 self.ST.Build(lst) else: self.lca_parents,self.lca_depth=self.SIV_DFS(s,parents=True,unweighted_dist=True) self.lca_PD=Path_Doubling(self.V,self.lca_parents) self.lca_PD.Build_Next(self.V) def LCA(self,a,b): if self.lca_segment_tree: m=min(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b]) M=max(self.lca_dfs_in_index[a],self.lca_dfs_in_index[b]) x=self.lca_euler_tour[self.ST.Fold_Index(m,M+1)] if x>=0: lca=x else: lca=self.lca_parents[~x] else: if self.lca_depth[a]>self.lca_depth[b]: a,b=b,a b=self.lca_PD.Permutation_Doubling(b,self.lca_depth[b]-self.lca_depth[a]) if a!=b: for k in range(self.lca_PD.k-1,-1,-1): if self.lca_PD.permutation_doubling[k][a]!=self.lca_PD.permutation_doubling[k][b]: a,b=self.lca_PD.permutation_doubling[k][a],self.lca_PD.permutation_doubling[k][b] a,b=self.lca_PD.permutation_doubling[0][a],self.lca_PD.permutation_doubling[0][b] lca=a return lca def Dijkstra(self,s,route_restoration=False): dist=[self.inf]*self.V dist[s]=0 queue=[(0,s)] if route_restoration: parents=[None]*self.V while queue: dx,x=heapq.heappop(queue) if dist[x]dx+dy: dist[y]=dx+dy if route_restoration: parents[y]=x heapq.heappush(queue,(dist[y],y)) if route_restoration: return dist,parents else: return dist N,K=map(int,readline().split()) graph=[[] for x in range(N+K)] for _ in range(N-1): A,B,C=map(int,readline().split()) A-=1;B-=1 graph[A].append((B,2*C)) graph[B].append((A,2*C)) G=Graph(N+K,graph=graph,directed=True,weighted=True) dist_T=G.SIV_DFS(0,weighted_dist=True) G.Build_LCA(0) for k in range(N,N+K): M,P=map(int,readline().split()) X=list(map(int,readline().split())) for m in range(M): X[m]-=1 graph[X[m]].append((k,P)) graph[k].append((X[m],P)) dist=[G.Dijkstra(k) for k in range(N,N+K)] Q=int(readline()) for q in range(Q): U,V=map(int,readline().split()) U-=1;V-=1 lca=G.LCA(U,V) ans=dist_T[U]+dist_T[V]-2*dist_T[lca] if K: ans=min(ans,min(dist[k][V]+dist[k][U] for k in range(K))) ans//=2 print(ans)