Mr. V

Mr. V received $n$ beads from his friends, each numbered from $1$ to $n$. 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.

Input

The first line contains a single integer $n$ ($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 $u$, $v$, and $l$ ($1\le u<v\le n$, $1\le l\le 10000$) — representing the beads connected by the thread and its length.

Output

Output a single integer — the maximum possible sum of the lengths of the blue threads in the necklace.

Examples

Note

In the first example, Mr. V could start with bead number $3$, connect it to bead number $5$ with a red thread, then disconnect beads $3$ and $5$ and connect beads $1$ to $3$ and $1$ to $5$ with blue threads. Next, connect beads $1$ and $2$ with a red thread, and finally connect beads $1$ and $4$ with a red thread. This results in a sum of $60$ for the lengths of the blue threads.

Scoring

1. ($13$ points): $1\le n\le 10$;

2. ($15$ points): $1\le n\le 200$;

3. ($29$ points): $1\le n\le 10000$;

4. ($43$ points): no additional constraints.