题目描述

りんごさん有一棵包含 $N$ 个顶点的树。这棵树的 $N-1$ 条边中，第 $i$ 条边连接顶点 $A_i$ 与顶点 $B_i$，边权为 $C_i$。另外，顶点 $i$ 有一个权值 $X_i$。

我们定义 $f(u,v)$ 为“从顶点 $u$ 到顶点 $v$ 的距离”与“$X_u + X_v$”的和。

请考虑一个包含 $N$ 个顶点的完全图 $G$。在 $G$ 中，顶点 $u$ 与顶点 $v$ 之间的边的代价为 $f(u,v)$。请你求出图 $G$ 的最小生成树的总代价。

输入格式

输入从标准输入读入，格式如下：

$N$ $X_1$ $X_2$ $\cdots$ $X_N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\cdots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出格式

输出图 $G$ 的最小生成树的总代价。

输入输出样例 #1

输入 #1

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

输出 #1

22

输入输出样例 #2

输入 #2

6
44 23 31 29 32 15
1 2 10
1 3 12
1 4 16
4 5 8
4 6 15

输出 #2

359

输入输出样例 #3

输入 #3

2
1000000000 1000000000
2 1 1000000000

输出 #3

3000000000

说明/提示

限制条件

• $2 \leq N \leq 200,\!000$
• $1 \leq X_i \leq 10^9$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 给定的图是一棵树。
• 所有输入都是整数。

样例解释 1

连接顶点 $1$ 和 $2$、顶点 $1$ 和 $4$、顶点 $3$ 和 $4$，分别的代价为 $5,8,9$，合计为 $22$。

由 ChatGPT 5 翻译