题目描述

This is Yet Another Tree Problem. You are given a tree, where every node has a penalty and every edge has a weight. The cost of a simple path between any two nodes is the sum of the weights of the edges in the path, plus the product of the penalties of the endpoint nodes. Note that a path can have $0$ edges, and the cost of such a path is simply the square of the penalty of the node.

For each node, compute the smallest cost of any path starting at that node. The final answer is the sum of all of these minimum costs.

输入格式

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of a single integer $n$ ($1 \leq n \leq 200,000$), which is the number of nodes. The next line will consist of $n$ space-separated integers $p$ ($1 \leq p \leq 1,000,000$), which is the penalty of each node, in order. Each of the following $n - 1$ lines will consist of three space-separated integers $i$, $j$ and $w$ ($1 \leq i \leq n$, $1 \leq j \leq n$, $i \neq j$, $1 \leq w \leq 1,000,000$), specifying an edge between nodes $i$ and $j$ with weight $w$.

输出格式

Output a single integer, which is the sum of all of the lowest cost paths for each node.

5
9 7 1 1 9
3 2 8
5 2 10
4 3 10
2 1 2

63