Description

In the era of Da Vinci, there was a popular children's game called Beads and Wires. As the name suggests, the game involves beads and wires. The wires are either red or blue, and the beads are numbered from $1$ to $n$. The game starts with a single bead, and each time a new bead is added using one of the following operations:

Append(w, v): Connect a new bead $w$ to an already added bead $v$ with a red wire.

Insert(w, u, v): Insert a new bead $w$ between two beads $u$ and $v$ that are connected by a red wire. Specifically, remove the red wire between $u$ and $v$, and connect $u$ to $w$ and $w$ to $v$ with blue wires.

Each wire has a length. After the game ends, your final score is the sum of the lengths of all blue wires.

You are given the final configuration of the Beads and Wires game: which beads are connected and the length of each wire. However, you are not told the color of each wire.

Your task is to write a program to find the maximum possible score. That is, among all games that could lead to the given final configuration, find the one with the highest score and output that maximum possible score.

Input Format

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

Each of the next $n - 1$ lines contains 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$. This means there is a wire of length $c_i$ between beads $a_i$ and $b_i$.

Output Format

Output a single integer, the maximum possible score.

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

60

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

140

Hint

[Sample Description 1]

A score of $60$ can be achieved as follows: start from bead $3$.

• Connect $5$ and $3$. (length arbitrary)
• Insert $1$ between $3$ and $5$. (the lengths are $40$ and $20$ respectively)
• Connect $2$ to $1$ with a wire of length $10$.
• Connect $4$ to $1$ with a wire of length $15$.

[Constraints]

• Subtask 1 (13 points): $1 \leq n \leq 10$.
• Subtask 2 (15 points): $1 \leq n \leq 200$.
• Subtask 3 (29 points): $1 \leq n \leq 10000$.
• Subtask 4 (43 points): $1 \leq n \leq 200000$.

Translated by ChatGPT 5