题目描述

给定一个由 $n$ 个顶点组成的无向图。每个顶点上都写有一个数，顶点 $i$ 上的数为 $a_i$。初始时图中没有边。

你可以向这个图中添加一些边，但需要为它们付费。在顶点 $x$ 和 $y$ 之间添加一条边的花费是 $a_x+a_y$ 枚硬币。

此外，还有 $m$ 个特殊优惠。每个优惠由三个数 $x$、$y$ 和 $w$ 表示，意思是你可以添加一条连接顶点 $x$ 和顶点 $y$ 的边，并为此支付 $w$ 枚硬币。你不一定要使用特殊优惠：即使顶点 $x$ 和 $y$ 之间存在特殊优惠，你仍然可以支付 $a_x+a_y$ 枚硬币来连接它们。

为了使这个图连通，你最少需要花费多少枚硬币？回忆一下，如果仅使用图中的边就可以从任意一个顶点到达任意另一个顶点，那么这个图就是连通的。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图中的顶点数和特殊优惠的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示写在各个顶点上的数。

接下来有 $m$ 行，每行包含三个整数 $x$、$y$ 和 $w$，表示一个特殊优惠：你可以添加一条连接顶点 $x$ 和顶点 $y$ 的边，这条边的花费为 $w$ 枚硬币。

输出格式

输出一个整数，表示为了使这个图连通，你最少需要支付的硬币数量。

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

说明 / 提示

在第一个样例中，可以使用第二个特殊优惠连接顶点 $1$ 和 $2$，然后在不使用任何优惠的情况下连接顶点 $1$ 和 $3$。

在接下来的两个样例中，最优答案可以在不使用特殊优惠的情况下得到。

数据范围

（$1\le n\le 2\cdot 10^5$，$0\le m\le 2\cdot 10^5$）

（$1\le a_i\le 10^{12}$）

（$1\le x,y\le n$，$1\le w\le 10^{12}$，$x\ne y$）