給定一棵樹，每條邊都有一個非負整數權重。 令 $d(u, v)$ 為頂點 $u$ 和 $v$ 之間唯一簡單路徑上邊權重的最大值。 在所有頂點的排列 $p_1, p_2, \dots, p_n$ 中，找出 $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ 的最大值。

輸入格式

第一行包含一個整數 $n$ ($2 \le n \le 100\,000$)：樹的頂點數量。 接下來的 $n-1$ 行，每行包含三個整數 $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

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

輸出格式 1

6

說明

在第一個範例中，其中一個最佳排列為 $\{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