暂无测试数据。

给你一个无向图，这个无向图有 $n$ 个顶点，每个顶点的权值为 $a_i$。

如果你要连接 $x,y$，那么需要花费 $a_x + a_y$ 的成本。或者给你 $m$ 条边 $x,y,w$，表示你如果连接 $x,y$ 需要花费 $w$，当然你也可以花费 $a_x + a_y$。那么请问把这 $n$ 个点连通的最小花费是多少？

输入格式

第一行输入两个整数 $n,m(1 \leq n \leq 2 \times 10 ^ 5, 0 \leq m \leq 2 \times 10 ^5) $，表示 $n$ 个顶点，$m$ 条边。

第二行输入 $n$ 个整数，表示顶点 $i$ 的权值为 $a_i(1 \leq a_i \leq 10 ^ {12})$。

接下来输入 $m$ 行，每行包括三个整数 $x,y,w(1 \leq x, y \leq n, 1 \leq w \leq 10 ^ {12}, x \neq y)$，表示如果连接 $x,y$ 需要花费 $w$。

输出格式

输出一个整数，表示把这 $n$ 个点连通的最小花费。

3 2
1 3 3
2 3 5
2 1 1

5

4 0
1 3 3 7

16