Problem Description

In the era of Leonardo da Vinci, there was a popular children's game called Beads and Strings. The game involves beads and strings, which can be red or blue. The beads are numbered from $1$ to $n$. The game starts with one bead and adds a new bead in one of the following ways:

Append(w, v): A new bead $w$ is connected to an existing bead $v$ with a red string.

Insert(w, u, v): A new bead $w$ is inserted between two beads $u$ and $v$ connected by a red string. Specifically, the red string between $u$ and $v$ is removed, and $u$ is connected to $w$ and $w$ to $v$ with blue strings.

Each string has a length. The final score of the game is the sum of the lengths of the blue strings.

Given the final state of the game, including the connections between beads and the lengths of the strings, but not the colors of the strings, you need to write a program to find the maximum possible score. That is, among all possible games that end in the given state, find the one with the highest score and output that maximum score.

Input Format

The first line contains a positive integer $n$, representing the number of beads, numbered from $1$ to $n$.

The next $n - 1$ lines each contain three integers $a_i, b_i, c_i$. It is guaranteed that $1 \leq a_i < b_i \leq n$ and $1 \leq c_i \leq 10000$. These integers indicate that there is a string of length $c_i$ connecting bead $a_i$ and bead $b_i$.

Output Format

Output a single integer, which is the maximum possible score.

Sample Input and Output

Sample Input #1

5
1 2 10
1 3 40
1 4 15
1 5 20

Sample Output #1

60

Sample Input #2

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

Sample Output #2

140

Notes

Sample Description 1

A score of $60$ can be achieved as follows: Start with bead $3$.

Connect bead $5$ to bead $3$. (String length is arbitrary)

Insert bead $1$ between beads $3$ and $5$. (String lengths are $40$ and $20$ respectively)

Connect bead $2$ to bead $1$ with a string of length $10$.

Connect bead $4$ to bead $1$ with a string of length $15$.

Constraints and Specifications

The first subtask is worth 13 points, with $1 \leq n \leq 10$.

The second subtask is worth 15 points, with $1 \leq n \leq 200$.

The third subtask is worth 29 points, with $1 \leq n \leq 10000$.

The fourth subtask is worth 43 points, with $1 \leq n \leq 200000$.

见题面 Input 部分

见题面 Output 部分