There are cities and they are connected by railways. In other words, the city and the railway form a tree.

There is a strange rule about the charging method in this place. The travel fare required for a passenger to travel kilometers is . Please note that passengers cannot divide a journey into several shorter journeys in order to achieve the purpose of reducing tolls.

There is an event to be held in this place. There are  contestants in the city. You have to choose a city to hold this event to minimize the sum of travel expenses for all contestants.

输入描述:

Enter an integer  on the first line.

The second line is  integers , separated by spaces.

In the next  line, each line contains three integers , indicating that there is a railway connecting cities  and  with a length of  kilometers.

输出描述:

Output one line, including an integer, which means the minimum toll.

Ensure that the answer range does not exceed the long long type.

3
1 1 1
1 2 10
2 3 10

200