Christmas Concert
Description
Nozomi will hold a concert on Christmas Eve. The audiences will come from n cities. More specifically, they know that there will be wi audiences coming from the i-th city.
n − 1 two-way roads connect these n cities in form. of a binary tree. It takes one unit time to travel from one city to another city if they are directly connected by a road.
As an assistant, Kyaru is asked to choose the best city to hold the concert, where the sum of time that it takes for each audience to get to the concert is minimized.
Input
The first line contains an integer n, indicating the number of cities.
Assume the first city to be the root of the tree, the i-th line of the following n lines contains
three integers wi , li , ri , where li , ri represents the indices of the two cities which are the two children of i-th city in this binary tree. Specially, li = 0 or ri = 0 means the i-th city doesn't have the corresponding child.
Output
One integer indicating the minimum sum of time.
Sample Input/Output
Input
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
Output
81
Constraint
1 ≤ n ≤ 5000, 0 ≤ wi ≤ 105 .