连通

题目描述

给定一个无向图，该图包含 $n$ 个顶点。每个顶点 $i$ 上写有一个数字 $a_i$。初始时图中没有任何边。

你可以向图中添加一些边，但需要为此支付费用。连接顶点 $x$ 和 $y$ 的边的费用为 $a_x + a_y$ 个金币。此外，还有 $m$ 个特殊优惠，每个优惠由三个数字 $x$、$y$ 和 $w$ 表示，意味着你可以用 $w$ 个金币连接顶点 $x$ 和 $y$。你可以选择是否使用这些特殊优惠：即使某对顶点 $x$ 和 $y$ 有特殊优惠，你仍然可以选择以 $a_x + a_y$ 的费用连接它们。

你的任务是求使图连通所需支付的最少金币数。回忆一下，如果从任意一个顶点出发都可以通过图中的边到达任意其他顶点，则该图是连通的。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^5$），分别表示图中的顶点数和特殊优惠的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{12}$），表示每个顶点上写的数字。

接下来 $m$ 行，每行包含三个整数 $x$、$y$ 和 $w$（$1 \le x, y \le n$，$1 \le w \le 10^{12}$，$x \ne y$），表示一个特殊优惠：你可以用 $w$ 个金币连接顶点 $x$ 和 $y$。

输出格式

输出一个整数，表示使图连通所需支付的最少金币数。

样例

3 2
1 3 3
2 3 5
2 1 1

5

4 0
1 3 3 7

16

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

18

说明/提示

在第一个样例中，可以使用第 $2$ 个特殊优惠连接 $1$ 和 $2$，然后再以普通费用连接 $1$ 和 $3$。

在接下来的两个样例中，最优解可以不使用任何特殊优惠。