Mr. V#10503
Mr. V received beads from his friends, each numbered from to . He connected these beads using (n-1) threads to create a necklace with a tree-like structure, as Mr. V is a programmer.
Here's how Mr. V constructed the necklace: He started with an initial bead and then added one bead at a time, (n-1) times. He could add a bead in one of two ways: either by selecting a bead already in the necklace and connecting it to a new bead with a red thread, or by choosing a pair of beads already connected by a red thread, disconnecting them, and then connecting each to the new bead with a blue thread.
The threads connecting the beads can vary in length.
Mr. V documented the necklace's structure and passed it to Mrs. V. However, he forgot the colors of the threads. Your task is to help him determine the maximum possible sum of the lengths of the blue threads in the necklace, as this is of particular interest to him.
The first line contains a single integer (1\le n\le 2\cdot 10^5) — the number of beads in the necklace.
Each of the next n-1 lines contains three integers , , and (1\le u<v\le n, 1\le l\le 10\,000) — representing the beads connected by the thread and its length.
Output a single integer — the maximum possible sum of the lengths of the blue threads in the necklace.
Example 1
Example 2
In the first example, Mr. V could start with bead number , connect it to bead number with a red thread, then disconnect beads and and connect beads to and to with blue threads. Next, connect beads and with a red thread, and finally connect beads and with a red thread. This results in a sum of for the lengths of the blue threads.
( points): 1\le n\le 10;
( points): 1\le n\le 200;
( points): 1\le n\le 10000;
( points): no additional constraints.