AT_cf17_final_j Tree MST

りんごさん有一棵包含 $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$ 的最小生成树的总代价。

## 限制条件 - $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 翻译