harurun君の家には一本の木が生えています。 harurun君はその木から最小のコストで手裏剣を作ることにしました。
頂点に $1,\dots,N$ の番号が、辺に $1,\dots,N-1$ の番号がついた $N$ 頂点の木グラフが与えられます。 辺 $i$ は頂点 $u_i, v_i$ を結び、重さは $w_i$ です。
ある頂点 $r$ を根とした根付き木を考えます。 このとき、次の操作を行えなくなるまで繰り返したときにかかるコストの総和の最小値を $c_{r}$ とします。 ただし、初めから操作を一度も行えないときは $c_{r}=0$ とします。
操作は有限回で終了することが証明できます。 $\min_{r\in\{1,2,\ldots,N\}}{c_{r}}$ を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて解いてください。
入力は以下の形式で標準入力から与えられます。
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
ただし、 $case_i$ は $i$ 個目のテストケースを表し、以下の形式で与えられます。
$N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
全体で $T$ 行出力してください。 $i$ 行目には、 $i$ 個目のテストケースに対する答えを出力してください。
3 5 1 2 3 2 3 1 3 4 4 3 5 2 4 1 2 1 3 2 1 2 4 -100 10 1 2 1 2 3 2 3 4 -5 4 5 -10 5 6 9 6 7 200 7 8 2 8 9 -20 9 10 100
3 -99 45
$1$ つ目のテストケースについて、 $(c_1,c_2,c_3,c_4,c_5)=(7, 6, 3, 6, 8)$ であるため、 $3$ を出力します。
$2$ つ目のテストケースについて、 $(c_1, c_2, c_3, c_4)=(-99, 0, -99, 2)$ であるため、 $-99$ を出力します。