注意

この問題の実行時間制限は $3$ 秒です。

問題文

I-wateには $N$ 個の街、$N-1$ 本の鉄道路線、$K$ 個の航空会社があります。

鉄道路線 $i(1\le i<N)$ は街 $A_i$ と街 $B_i$ を結んでいて、$C_i$ 円支払うと、街 $A_i$ と街 $B_i$ を相互に行き来できるようになります。 また、どの街同士も鉄道路線のみで行き来できるようになっています。

航空会社 $i(1\le i\le K)$ は $M_i$ 個の街 $X_{i,1},X_{i,2},\dots ,X_{i,M_i}$ に空港を持っていて、 $P_i$ 円支払うと、航空会社 $i$ が空港を持つ $M_i$ 個の街のうちどの街からどの街へも移動できるようになります。

次の春にI-wate旅行をする予定のVil君は、現在ある旅行計画候補のうちどれを選ぶか決めかねています。 計画選定のため、Vil君は $Q$ 個の街のペア $(U_1,V_1),(U_2,V_2),\dots ,(U_Q,V_Q)$ それぞれについて、一方から他方への移動にかかる金額の最小値を知りたいと思っています。 計算が苦手なVil君の代わりにこれらを求めてあげてください。

入力

$NK$
$A_1{B}_1{C}_1$
$A_2{B}_2{C}_2$
$⋮$
$A_{N-1}{B}_{N-1}{C}_{N-1}$
$M_1{P}_1$
$X_{1,1}{X}_{1,2}\dots X_{1,M_1}$
$M_2{P}_2$
$X_{2,1}{X}_{2,2}\dots X_{2,M_2}$
$⋮$
$M_K{P}_K$
$X_{K,1}{X}_{K,2}\dots X_{K,M_K}$
$Q$
$U_1{V}_1$
$U_2{V}_2$
$⋮$
$U_Q{V}_Q$

• 入力はすべて整数
• $2\le N\le {10}^5$
• $0\le K\le 10$
• $1\le A_i<B_i\le N$
• $1\le C_i\le {10}^9$
• どの街同士も鉄道路線のみで互いに行き来できる
• $2\le M_i\le N$
• ${\displaystyle \sum _{i=1}^K{M}_i\le {10}^5}$
• $1\le P_i\le {10}^9$
• $1\le X_{i,j}\le N$
• $j\ne k$ ならば $X_{i,j}\ne X_{i,k}$
• $1\le Q\le {10}^5$
• $1\le U_i<V_i\le N$

出力

$Q$ 行出力してください。

$i(1\le i\le Q)$ 行目には街 $U_i$ から街 $V_i$ に移動するために必要な最小金額を出力し、最後に改行してください。

サンプル

5 1
1 4 6
3 5 12
1 2 8
2 3 2
4 10
2 4 5 3
3
1 3
1 4
1 5

10
6
16

7 2
4 7 2
2 5 5
3 6 14
1 2 16
2 3 6
2 4 17
3 1
5 7 3
3 3
3 7 2
6
4 7
1 2
1 3
2 6
1 5
3 7

2
16
19
17
20
1