Sleigh Ride

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 32M

Problem type

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

0 1 1
0 2 1

Sample Output


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).


There are no comments at the moment.