問題文

$N$ 個の電波塔があり、各電波塔はそれぞれ $1\sim N$ の番号が付いています。

各電波塔は、ある正整数 $r$ を半径とした円内(円周も含む)に電波を飛ばすことが出来ます。

あなたは各電波塔間に好きな数、双方向の通信路を建設することができます。

電波塔 $a_i$ と $b_i$ の間に通信路を建設する場合、$a_i$$b_i$ 間の距離 $C_i$ と等しいコストがかかります。$(1\le i\le N(N-1)/2)$

電波塔 $x$ と電波塔 $y$ は以下の条件のどちらかを満たすとき双方向に通信することができます。

• $x$$y$ 間に通信路が建設されていて、 $x$$y$ 間の距離が $r$ 以下である。

• $x,y$ を含まない $k(>0)$ 個の電波塔 $(t_1,t_2,...,t_k)$ を選ぶ。 このとき、$x$$t_1$ 間、$t_1$$t_2$ 間、...、$t_k$$y$ 間の全てに通信路が建設されていて、 $x$$t_1$ 間、$t_1$$t_2$ 間、...、$t_k$$y$ 間のそれぞれの距離が全て $r$ 以下である。

あなたの目標は、任意の電波塔間の通信を可能にすることです。

かかるコストの総和が最小になるように通信路を建設したときの、正整数 $r$ の最小値を求めてください。

ただし、コストの総和が最小になる建設の仕方が複数ある場合は、それぞれの建設の仕方の正整数 $r$ の最小値を求め、その中での最小値を求めてください。

制約

• $2\le N\le {10}^2$

• $a_i\ne b_i$

• 任意の異なる $i,j$ について $\{a_i,b_i\}\ne \{a_j,b_j\}$

• $1\le a_i,b_i\le N$

• $\mathbf{1}\mathbf{\le }{\mathit{C}}_{\mathbf{1}}\mathbf{<}{\mathit{C}}_{\mathbf{2}}\mathbf{<}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{<}{\mathit{C}}_{\mathit{N}\mathbf{(}\mathit{N}\mathbf{-}\mathbf{1}\mathbf{)}/\mathbf{2}}\mathbf{\le }{\mathbf{10}}^{\mathbf{100}}$

• 入力は全て整数

入力

$N$
$a_1{b}_1{C}_1$
$a_2{b}_2{C}_2$
$⋮$
$a_{N(N-1)/2}{b}_{N(N-1)/2}{C}_{N(N-1)/2}$

• $1$ 行目には 電波塔の数が与えられる。

• $2$ から $N(N-1)/2+1$ 行目には、$a_i,b_i,C_i$ が空白区切りで与えられ、電波塔 $a_i$ と電波塔 $b_i$ の距離が $C_i$ であることを表す。

出力

答えを１行に出力してください。最後に改行してください。

サンプル

2
1 2 1

1

5
1 2 2
1 3 3
2 4 4
3 5 5
1 4 6
1 5 7
2 3 8
2 5 9
3 4 10
4 5 11

5