Vous disposez d'un arbre, et chaque arête possède un poids entier non négatif.

Soit $d(u, v)$ le poids maximum des arêtes sur l'unique chemin simple entre les sommets $u$ et $v$.

Trouvez la plus grande valeur de $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ parmi toutes les permutations des sommets $p_1, p_2, \dots, p_n$.

Entrée

La première ligne contient un entier $n$ ($2 \le n \le 100\,000$) : le nombre de sommets dans l'arbre.

Chacune des $n - 1$ lignes suivantes contient trois entiers $u, v, w$ ($1 \le u, v \le n$, $0 \le w \le 30$), représentant une arête dans l'arbre reliant les sommets $u$ et $v$ avec un poids $w$.

Sortie

Affichez un entier : la plus grande valeur de $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$.

Exemples

Entrée 1

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

Sortie 1

6

Entrée 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

Sortie 2

42

Remarque

Dans le premier exemple, l'une des permutations optimales est $\{4, 5, 3, 2, 1\}$.