Se te da un árbol, y cada arista tiene un peso entero no negativo.

Sea $d(u, v)$ el máximo de los pesos de las aristas en el camino simple único entre los vértices $u$ y $v$.

Encuentra el mayor valor de $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ entre todas las permutaciones de vértices $p_1, p_2, \dots, p_n$.

Entrada

La primera línea contiene un entero $n$ ($2 \le n \le 100\,000$): el número de vértices en el árbol.

Cada una de las siguientes $n - 1$ líneas contiene tres enteros $u, v, w$ ($1 \le u, v \le n$, $0 \le w \le 30$), que representan una arista en el árbol con extremos $u, v$ y peso $w$.

Salida

Imprime un entero: el mayor valor de $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$.

Ejemplos

Entrada 1

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

Salida 1

6

Entrada 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

Salida 2

42

Nota

En el primer ejemplo, una de las permutaciones óptimas es $\{4, 5, 3, 2, 1\}$.