代写Christmas Concert代写留学生Matlab语言

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 .