시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

You are given a tree, and each edge has a non-negative integer weight.

Let $d(u, v)$ --- The maximum of the edge weights on the unique simple path between vertices $u$ and $v$.

Find the largest $\sum_{i=2}^n{2^{d(p_{i - 1}, p_i)}}$ among all permutations of vertices $p_1, p_2, \ldots, p_n$.

입력

The first line contains one integer $n$ ($2 \leq n \leq 100\,000$): the number of vertices in the tree.

Each of the next $n-1$ lines contains three integers $u,v,w$ ($1 \leq u, v \leq n, 0 \leq w \leq 30$), an edge in the tree with endpoints $u,v$ having weight $w$.

출력

Print one integer: the largest $\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

힌트

In the first example, one of the optimal permutations is $\{4, 5, 3, 2, 1\}$.