Great Cow Gathering

Bessie is planning the annual Great Cow Gathering and wants to choose the most convenient barn to host it.

Every cow lives in one of $N$ barns, numbered $1$ through $N$. The barns are connected by $N-1$ roads so that you can travel between any two barns. Road $i$ connects barns $A_i$ and $B_i$ and has length $L_i$; the barns therefore form a tree. Barn $i$ is home to $C_i$ cows.

The gathering may be held in any single barn. If it is held in barn $X$, its inconvenience is the total distance every cow must travel to reach $X$: a barn holding $C_i$ cows at distance $d$ from $X$ contributes $C_i \cdot d$. For example, if $3$ cows live in a barn $20$ units away from $X$, they add $3 \times 20 = 60$ to the inconvenience.

Choose the barn that minimizes the total inconvenience, and report that minimum inconvenience.

Constraints

• $1 \le N \le 100{,}000$
• $1 \le A_i, B_i \le N$
• $1 \le L_i \le 1{,}000$
• $0 \le C_i \le 1{,}000$

• Line $1$: a single integer $N$.
• Lines $2$ to $N+1$: line $i+1$ contains a single integer $C_i$, the number of cows in barn $i$.
• Lines $N+2$ to $2N$: each of these $N-1$ lines contains three integers $A_i$, $B_i$, and $L_i$, describing a road of length $L_i$ between barns $A_i$ and $B_i$.

• A single line containing the minimum possible inconvenience.