There's a big apple tree in the forest. In the tree there are N nodes (numbered from 0 to N - 1), and the nodes are connected by branches. On each node of the tree, there is a squirrel. In the autumn, some apples will grow on the nodes. After all apples are ripe, each squirrel will collect all the apples of their own node and store them. For the demand to be harmonic, they decide to redistribute the apples to minimize the variance (please refer to the hint) of apples in all nodes. Obviously, an apple cannot be divided into several parts. To reach this goal, some transportation should be taken. The cost of transporting x apples from node u to node v is x * distance (node u, node v). Now given the current amount of apples of each node and the structure of the apple tree, you should help the squirrels to find the minimal cost to redistribute the apples.
Input
Input consists of multiple test cases (less than 80 cases)!
For each test case, the first line contains an integer N (1 <= N <= 100), which is the number of the nodes in the tree.
The following line contains N integers a0,a1,...,aN-1 (0 <= ai <= 10000), representing the amount of the i-th node's apples.
The following N - 1 lines each contain three integers u, v, c (0 <= u,v <= N - 1, 0 <= c <= 1000), which means node u and node v are connected by a branch, the length of the branch is c.
There is a blank line between consecutive cases.
Output
For each case output the minimal total transportation cost. The minimal cost is guaranteed to be less than 231.
Sample Input
3
1 2 3
0 1 1
0 2 1
3
1 3 3
0 1 3
0 2 4
2
1 2
0 1 1
Sample Output
1
3
0