Winter has come to Bajtocja. Bajtazar, a snowplow driver, was not caught off guard and set out to clear the streets of Bajtogród.

The road network in Bajtogród consists of $n$ intersections connected by $n-1$ bidirectional streets. From every intersection, it is possible to reach any other intersection by exactly one path consisting of one or more streets without turning back.

Snow falls continuously, so the streets must be constantly cleared again. For each street, Bajtazar knows the minimum number of times it must be cleared during the day (it does not matter to him at what moments of the day he does this). Bajtazar can start clearing at any intersection. He would like to plan his work so that the total number of streets traversed is as small as possible. Naturally, traversing the same street multiple times counts multiple times.

Input

The first line of input contains a single integer $n$ ($2 \le n \le 500\,000$) representing the number of intersections in Bajtogród. The next $n-1$ lines describe the individual streets. Each of these lines contains three integers $a_{i}$, $b_{i}$, $d_{i}$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le d_i \le 100\,000$) indicating that intersections $a_{i}$ and $b_{i}$ are connected by a bidirectional street that must be cleared at least $d_{i}$ times during the day.

Output

Output a single line containing the minimum number of streets Bajtazar must traverse to satisfy the given requirements.

Examples

Input 1

6
1 2 1
2 3 1
3 5 2
5 4 1
5 6 1

Output 1

8

Note

Bajtazar's optimal route traverses eight streets: 1 → 2 → 3 → 5 → 4 → 5 → 6 → 5 → 3.