PowerOutage

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

You work for an electric company, and the power goes out in a rather large apartment complex with a lot of irate tenants. You isolate the problem to a network of sewers underneath the complex with a step-up transformer at every junction in the maze of ducts. Before the power can be restored, every transformer must be checked for proper operation and fixed if necessary. To make things worse, the sewer ducts are arranged as a tree with the root of the tree at the entrance to the network of sewers. This means that in order to get from one transformer to the next, there will be a lot of backtracking through the long and claustrophobic ducts because there are no shortcuts between junctions. Furthermore, it\'s a Sunday; you only have one available technician on duty to search the sewer network for the bad transformers. Your supervisor wants to know how quickly you can get the power back on; he\'s so impatient that he wants the power back on the moment the technician okays the last transformer, without even waiting for the technician to exit the sewers first.Your technician will start at junction 0 which is the root of the sewer system. Your goal is to calculate the minimum number of minutes it will take for your technician to check all of the transformers. 

Input

 Please note there are multi test cases. 
In each test case, you will first get N, Then N line.Each line conten three integer F T D, means from F to T need D minutes.
 

Output

 You will get an int that represents this minimum number of minutes.

Sample Input

3
0 1 10
1 2 10
0 3 10
5
0 1 10
0 3 10
0 4 100
1 2 10
4 5 5

Sample Output

40
165

Hint

 Hint: In first case. Starting at junction 0, if the technician travels to junction 3 first, then backtracks to 0 and travels to junction 1 and then junction 2, all four transformers can be checked in 40 minutes, which is the minimum.

Source