Дано дерево, каждое ребро которого имеет неотрицательный целочисленный вес. Пусть $d(u, v)$ — максимальный из весов ребер на единственном простом пути между вершинами $u$ и $v$. Найдите наибольшее значение $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ среди всех перестановок вершин $p_1, p_2, \dots, p_n$.

Входные данные

Первая строка содержит одно целое число $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