Beads and Wires

Time limit1sMemory limit128 MB

Summary

You choose append and insert orders that build the given weighted tree to maximize the total length of insert-created edges.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, Greedy, Sorting
Solved: No attempts yet

Problem

In the bead-threading game, thread comes in red and blue. Beads are numbered $1$ through $n$ . You start with one bead and may add beads using:

Append(w, v): connect new bead $w$ to existing bead $v$ with a red thread.
Insert(w, u, v): insert new bead $w$ between beads $u$ and $v$ that are connected by red thread. Remove the red thread $u$ - $v$ and replace it with blue threads $u$ - $w$ and $w$ - $v$ .

Every thread has a length. When the game ends, the score is the sum of blue thread lengths.

You are given a final connection state: each thread connects two beads with a length, but colors are unknown. Among all ways to produce this state, output the maximum possible final score.

Input

Line 1: $n$ ( $1 \le n \le 200\,000$ ).

Next $n-1$ lines: $a_i$ , $b_i$ , $c_i$ ( $1 \le a_i < b_i \le n$ , $1 \le c_i \le 10\,000$ ). Beads $a_i$ and $b_i$ are connected by a thread of length $c_i$ .

Output

Print the maximum possible final score.

Hint

In the sample, start at bead 3, connect 5, insert 1 between 3 and 5, then append 2 and 4 to 1 for a score of 60. No larger score exists.

Examples6

Example 1
Input
```
5
1 2 10
1 3 40
1 4 15
1 5 20
```
Expected output
```
60
```
Example 2
Input
```
2
1 2 7
```
Expected output
```
0
```
Example 3
Input
```
3
1 2 5
2 3 8
```
Expected output
```
13
```
Example 4
Input
```
4
1 2 10
1 3 20
1 4 30
```
Expected output
```
50
```
Example 5
Input
```
6
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
```
Expected output
```
14
```

Example 6

Input

Expected output