Dano jest drzewo, w którym każda krawędź ma nieujemną wagę całkowitą.

Niech $d(u, v)$ oznacza maksymalną wagę krawędzi na jedynej ścieżce prostej między wierzchołkami $u$ oraz $v$.

Znajdź największą wartość sumy $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ dla wszystkich permutacji wierzchołków $p_1, p_2, \dots, p_n$.

Wejście

W pierwszej linii znajduje się jedna liczba całkowita $n$ ($2 \le n \le 100\,000$): liczba wierzchołków w drzewie.

Każda z kolejnych $n-1$ linii zawiera trzy liczby całkowite $u, v, w$ ($1 \le u, v \le n$, $0 \le w \le 30$), oznaczające krawędź w drzewie o końcach $u, v$ i wadze $w$.

Wyjście

Wypisz jedną liczbę całkowitą: największą wartość $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$.

Przykład

Wejście 1

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

Wyjście 1

6

Wejście 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

Wyjście 2

42

Uwagi

W pierwszym przykładzie jedną z optymalnych permutacji jest $\{4, 5, 3, 2, 1\}$.