Beads and Wires

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.

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$.

Print the maximum possible final score.

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.