注意

問題文

2019/10/4 21:46 問題文を修正しました．

niuez くんの住む街ではとある伝統があります．
街に生えている木から縁起の良い $3$ 頂点を含むように，なるべく小さく木を切り出して神木への「三つ木もの（みつぎもの）」（tri-butree）にするというものです．

$0$ から $N-1$ までの番号のついた $N$ 頂点，$N-1$ 辺からなる無向木があり，$i(0\le i<N-1)$番目の辺は頂点 $u_i$ と $v_i$ を端点とし，$w_i$ の重みを持っています．
以下の $Q$ 個の $\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}$ を処理してください．

• $xyz$

  • 木の連結成分のうち，互いに異なる頂点 $x,y,z$ が含まれていて，かつ頂点数が最小であるような木の連結な部分グラフに含まれる辺の重みの総和を求める（2019/10/4 21:44 用語の誤りを修正しました）．
  • このような木の連結な部分グラフは一意に定まることが証明出来ます．

入力

$N$
$u_0{v}_0{w}_0$
$\cdots$
$u_{N-2}{v}_{N-2}{w}_{N-2}$
$Q$
$x_0{y}_0{z}_0$
$\cdots$
$x_{Q-1}{y}_{Q-1}{z}_{Q-1}$

• $3\le N\le {10}^5$
• $0\le u_i,v_i<N$
  • $u_i\ne v_i$
  • $(u_i,v_i)=(u_j,v_j)\iff i=j$
• $1\le w_i<{10}^9$
• $1\le Q\le {10}^5$
• $0\le x_i,y_i,z_i<N$
  • $x_i,y_i,z_i$ は互いに相異なる
• 入力はすべて整数

出力

$Q$ 行出力し，$i$ 行目には $i$ 番目の $\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}$ の答えを整数で一行に出力してください．

サンプル

サンプル1

入力サンプルをコピー

入力

7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
3
0 1 2
0 3 4
3 5 6

出力

3
8
17

最初のクエリで, 頂点数が最小の連結成分は, 頂点$0,1,2$からなる連結成分です.
その連結成分に含まれる辺の重みの総和は$1+2=3$です.
次のクエリでは, 頂点$0,1,3,4$からなる連結成分です.
含まれる辺の重みの総和は$1+3+4=8$です.
3つめのクエリでは, 頂点$0,1,2,3,5,6$からなる連結成分です.
含まれる辺の重みの総和は$1+3+2+5+6=17$です.