重み付きの木が与えられる。各辺の重みは非負整数である。 $d(u, v)$ を、頂点 $u$ と頂点 $v$ を結ぶ唯一の単純パス上の辺の重みの最大値とする。 頂点のすべての順列 $p_1, p_2, \dots, p_n$ の中で、$\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ の最大値を求めよ。

入力

1行目に整数 $n$ ($2 \le n \le 100\,000$) が与えられる。これは木の頂点数である。 続く $n-1$ 行の各行には、3つの整数 $u, v, w$ ($1 \le u, v \le n, 0 \le w \le 30$) が与えられる。これは、端点が $u, v$ で重みが $w$ である木上の辺を表す。

出力

$\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ の最大値を1つの整数として出力せよ。

入出力例

入力 1

5
1 2 0
2 3 0
3 4 0
4 5 1

出力 1

6

注記

最初の例において、最適な順列の1つは $\{4, 5, 3, 2, 1\}$ である。

入力 2

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

出力 2

42