Description

Bessie is planning the annual grand cow gathering, with cows coming from all over the country. Of course, she will choose the most convenient place to hold it.

Each cow lives on one of the $N$ farms, which are connected by $N-1$ roads so that any farm is reachable from any other. Road $i$ connects farms $A_i$ and $B_i$ with length $L_i$. The gathering may be held at any of the $N$ farms. In addition, farm $i$ contains $C_i$ cows.

When choosing the location, Bessie wants to maximize convenience (that is, minimize inconvenience). If farm $X$ is chosen as the location, its inconvenience is the sum, over all other farms, of the distance each cow must travel to attend. For example, if the distance from farm $i$ to farm $X$ is $20$, then the total distance contributed by farm $i$ is $C_i \times 20$. Help Bessie find the most convenient farm for the gathering.

Input Format

• Line 1: an integer $N$.
• Lines 2 to $N+1$: line $i+1$ contains a single integer $C_i$.
• Lines $N+2$ to $2N$: line $i+N+1$ contains $3$ integers $A_i$, $B_i$, and $L_i$.

Output Format

A single line containing one integer, the minimum inconvenience.

5 
1 
1 
0 
0 
2 
1 3 1 
2 3 2 
3 4 3 
4 5 3 

15 

Hint

Constraints

$1 \leq N \leq 10^5$, $1 \leq A_i \leq B_i \leq N$, $0 \leq C_i, L_i \leq 10^3$.

Translated by ChatGPT 5