Statement

This is supposed to be Problem B

"Some people choose to live as dragons. But I think you live as a human" -- Mononobe Yuu

Doragon is a aqua dragon girl who lives in a peaceful village. Today she wants to show her friend Ookami around.

There are N houses and N-1 bidirectional roads in the village, each road has a length of positive integer. Her tour plan goes as follows:

• Start at a house to have breakfast
• Move along some roads so that each house is visited at least once
• End at a house to have lunch

If the starting and ending point can be chosen to be anywhere, Doragon wants to know what's the minumum total distance they will need to walk(or fly i don't care).

Input

The first line contains one integer N

The next N-1 line, each line contains u,v,w describing a road

Output

Output the minimal total walk distance

Example

[Input]
5
1 2 2 
2 3 4
2 4 3
1 5 5
[Output]
17
[Explain]
The optimal way is 5->1->2->4->2->3. See the picture below for detail:

Subtask

• For 40%, $1\leq N\leq 1000$

• For 100%, $1\leq N\leq 10^5$

$1\leq W\leq 10^9$