Now that Santa's put all the presents in his magic bag, he's going to go deliver the presents!
Of course, he's going to fly in the sky with the help of his trusty reindeer.
(How he delivers everything in time is another story…)

Santa starts at the North Pole, and must visit several (~N~) locations.
But he can't just travel however he wants.
Terrorists might try hunting him, or he might get shot down in protected airspace…
Also, some routes are really slow because of air currents.
Thus Santa has exactly ~N~ possible routes to travel. (However, it's still guaranteed he'll be able to deliver everything)
The routes are all two-way.

Given a list of these routes, output the time it takes for Santa to deliver the presents to every location!
Santa can visit places in any order, though.

Input Specification

~N~ (number of locations, ~1 \le N \le 100\,000~).
~N~ lines, each with three integers ~a,b,c~ ~(0 \le a,b \le N, 0 \le c \le 1\,000)~.
Each line represents a route between locations ~a~ and ~b~, that takes ~c~ seconds to traverse.
(Location ~0~ is the North Pole)

Output Specification

The minimum time it takes to deliver presents everywhere.
He won't have to return to the North Pole.

Sample Input

2
0 1 1
0 2 1

Sample Output

3

Santa goes from the North Pole to location ~1~ (~1~ second), back to the North Pole (~1~ second), and finally to location ~2~ (~1~ second).