Maximum Blue Score in the Beaded Line Game

In the Da Vinci era, a popular children’s game called 连珠线 (Beaded Line) was played with beads and threads. In this game, there are n beads numbered from $1$ to $n$, and threads that come in two colors: red and blue. The game starts with a single bead and then new beads are added one by one using one of the following operations:

• Append(w, v): A new bead $w$ is added and connected to an already present bead $v$ with a red thread.
• Insert(w, u, v): A new bead $w$ is inserted between two beads $u$ and $v$ that were originally connected by a red thread. The red thread between $u$ and $v$ is removed and two blue threads are added connecting $u$ with $w$ and $w$ with $v$, respectively.

After all moves, the final configuration is a tree of n beads and n-1 threads, with each thread having a given length, but the colors are not specified. The final score is the sum of the lengths of the blue threads. Your task is to determine the maximum possible score. In other words, among all possible sequences of moves that result in the given tree (ignoring thread colors), compute the maximum possible sum of blue thread lengths.

Game constraints and observations:

• An Append move always introduces a red thread.
• An Insert move removes an existing red thread and replaces it with two blue threads. Hence, blue threads always appear in pairs associated with the bead that was inserted by an Insert move.
• A bead added by an Insert move must have exactly two incident blue threads. Moreover, during the game the bead which receives blue threads cannot be adjacent to another bead added by an insertion (since in any Insert move, the two beads at the ends of the replaced red thread must already have been present and thus cannot be counted as inserted).

This implies that in any valid sequence:

• Beads that were added by an Append move (and the initial bead) are non‐inserted and all their incident threads in the final tree are red.
• Beads that were added via an Insert move (we call them inserted beads) must have degree exactly $2$, and both of their incident threads must be blue. Furthermore, an inserted bead is connected only to non‐inserted beads.

The decision variable is essentially which beads (other than the initial one) to consider as inserted so that their two incident edges become blue. For any bead v that is eligible (i.e. has degree exactly 2), if we choose to consider it as inserted, we add a contribution equal to the sum of the lengths of its two incident edges. However, if two eligible beads are adjacent in the tree then they share an edge. Since an edge may only be blue once (it is produced by a single insertion), they cannot both be chosen. Hence, the problem reduces to selecting an independent set among the vertices with degree $2$ in the tree (where an edge exists between two candidates if they are adjacent in the tree), such that the sum of the contributions, with the contribution of a vertex $v$ being the sum of the lengths of its incident edges, is maximized.

The input gives you the tree (the connectivity and the length of each thread). Compute the maximum total blue score, i.e. the maximum possible sum of lengths of blue threads, over all valid interpretations of the game.

inputFormat

The input begins with a single integer n ($2 \le n \le 10^5$) indicating the number of beads. The next n-1 lines each contain three integers u v w, describing an edge between beads u and v with length w (where w is a positive integer). It is guaranteed that the given edges form a tree.

outputFormat

Output a single integer — the maximum possible total length of blue threads.

sample

2
1 2 5

0