YATP

Here is yet another tree problem. You are given a tree in which every node has a penalty and every edge has a weight. The cost of a simple path between two nodes is the sum of the weights of the edges on that path plus the product of the penalties of the two endpoints. For nodes $u$ and $v$ the cost is $\mathrm{dist}(u, v) + p_u \times p_v$, where $\mathrm{dist}(u, v)$ is the sum of the edge weights on the path and $p_u$ is the penalty of node $u$.

A path may contain no edges at all. The cost of such a path is the square of that node's penalty, that is $p_u^2$.

For each node, find the smallest cost among the paths that start at that node. The final answer is the sum of those minimum costs over all nodes.

The input consists of a single test case.

The first line contains one integer $n$, the number of nodes. ($1 \le n \le 200{,}000$)

The second line contains $n$ space separated integers $p$, the penalty of each node in order of node number. ($1 \le p \le 1{,}000{,}000$)

Each of the next $n - 1$ lines contains three space separated integers $i$, $j$ and $w$, describing an edge between node $i$ and node $j$ with weight $w$. ($1 \le i \le n$, $1 \le j \le n$, $i \ne j$, $1 \le w \le 1{,}000{,}000$)

Print a single integer, the sum of the lowest path cost of every node.