’S No Problem

The Yllihc Engineering and Technological Institute (YETI), located in northern Snowblovia, has two problems: snow and money. Specifically, it has too much of the former and not enough of the latter. Every winter (and fall and spring, for that matter) the campus is covered with blankets of snow, and the sidewalks connecting campus buildings become impassable. To keep functioning, YETI needs to clear the snow from the sidewalks connecting the campus buildings. Since the budget is tight, these sidewalks form a minimal set that allows a path to exist between any two buildings.

With the money saved by not building more sidewalks, YETI bought two snow blowers. To clear the snow with them, two staff members take the two snow blowers out of the building (or buildings) where they are stored and push them along the sidewalks, clearing the snow. Each sidewalk must be traversed at least once. Each snow blower, once it has finished, is stored in the building it is currently next to (and during the next snowfall, the snow blowers will be pushed in the reverse direction, and so on, throughout the eleven months of the snow season).

The YETI maintenance crew want to choose the storage buildings of the snow blowers and design the routes along which they will be pushed, so that they minimize the total distance the two machines travel out in the cold (to protect both the precious equipment and the staff members from freezing). The routes might involve pushing along already-cleared sidewalks, as Figure J.1 shows, which gives an optimal solution for the sidewalk layout of Sample Input 1.

Figure J.1: Illustration of Sample Input 1 showing one possible pair of optimal routes.

YETI would ask its Computer Science Department to figure this out, but that department was wiped out in the Great Blizzard of ’06, so YETI has come to you for help.

The first line of input contains an integer n (4 ≤ n ≤ 100 000), the number of buildings on the YETI campus. Buildings are numbered from 1 to n. Each of the remaining n − 1 lines contains three integers a, b, and d indicating that a sidewalk of length d exists between buildings a and b (1 ≤ a, b ≤ n; a ≠ b; 1 ≤ d ≤ 500).

Output the minimum total distance the snow blowers must travel to remove snow from all sidewalks.