这是一个“又一个树问题”（Yet Another Tree Problem）。给定一棵树，每个节点都有一个惩罚值，每条边都有一个权重。任意两个节点之间简单路径的代价定义为：路径上所有边的权重之和，加上路径两个端点惩罚值的乘积。注意，路径可以包含 0 条边，此时路径的代价即为该节点惩罚值的平方。

对于每个节点，计算从该节点出发的所有路径中的最小代价。最终答案为所有这些最小代价之和。

输入格式

每个输入包含一个测试用例。注意，程序可能会在不同的输入上运行多次。输入的第一行包含一个整数 $n$ ($1 \le n \le 200,000$)，表示节点的数量。下一行包含 $n$ 个空格分隔的整数 $p$ ($1 \le p \le 1,000,000$)，依次表示每个节点的惩罚值。接下来的 $n - 1$ 行，每行包含三个空格分隔的整数 $i, j$ 和 $w$ ($1 \le i \le n, 1 \le j \le n, i \neq j, 1 \le w \le 1,000,000$)，表示节点 $i$ 和节点 $j$ 之间存在一条权重为 $w$ 的边。

输出格式

输出一个整数，即每个节点的最小路径代价之和。

样例

样例输入 1

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

样例输出 1

63