음이 아닌 정수 가중치를 가진 간선들로 이루어진 트리가 주어집니다. $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

입력 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

참고

첫 번째 예제에서 최적의 순열 중 하나는 $\{4, 5, 3, 2, 1\}$입니다.