题目描述

Ringo有一个包含 $N$ 个顶点的树。树中的第 $N-1$ 条边中的第 $i$ 条边连接了顶点 $A_i$ 和顶点 $B_i$，并且具有权重 $C_i$。此外，顶点 $i$ 的权重为 $X_i$。

在这里，我们定义 $f(u,v)$ 为顶点 $u$ 和顶点 $v$ 之间的距离加上 $X_u + X_v$。

我们将考虑一个完全图 $G$，它有 $N$ 个顶点。连接顶点 $u$ 和顶点 $v$ 的边的代价为 $f(u,v)$。找到 $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$
• 给定的图是一棵树。
• 所有输入值都是整数。

输入

从标准输入中以以下格式给出输入：

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

输出

打印 $G$ 的最小生成树的代价。

示例输入 1

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

示例输出 1

22

我们连接了以下顶点对：顶点 $1$ 和 $2$，顶点 $1$ 和 $4$，顶点 $3$ 和 $4$。它们的代价分别为 $5$，$8$ 和 $9$，总共为 $22$。

示例输入 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

2
1000000000 1000000000
2 1 1000000000

示例输出 3

3000000000