재미있는 외판원

트리가 주어지며, 각 간선에는 0 이상의 정수 가중치가 있다.

$d(u, v)$를 정점 $u$와 $v$를 잇는 유일한 단순 경로 위 간선 가중치의 최댓값이라고 하자.

정점의 모든 순열 $p_1, p_2, \ldots, p_n$에 대해 $\sum_{i=2}^n 2^{d(p_{i-1}, p_i)}$의 최댓값을 구하시오.

첫 줄에 정점의 개수 $n$ ($2 \leq n \leq 100\,000$)이 주어진다.

다음 $n-1$개 줄에는 세 정수 $u, v, w$ ($1 \leq u, v \leq n$, $0 \leq w \leq 30$)가 주어진다. 이는 양 끝점이 $u$와 $v$이고 가중치가 $w$인 간선을 뜻한다.

$\sum_{i=2}^n 2^{d(p_{i-1}, p_i)}$의 최댓값을 정수 하나로 출력한다.

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