CF1095F.Make It Connected

You are given an undirected graph consisting of $n$ vertices. A number is written on each vertex; the number on vertex $i$ is $a_i$. Initially there are no edges in the graph.

You may add some edges to this graph, but you have to pay for them. The cost of adding an edge between vertices $x$ and $y$ is $a_x + a_y$ coins. There are also $m$ special offers, each of them is denoted by three numbers $x$, $y$ and $w$, and means that you can add an edge connecting vertices $x$ and $y$ and pay $w$ coins for it. You don't have to use special offers: if there is a pair of vertices $x$ and $y$ that has a special offer associated with it, you still may connect these two vertices paying $a_x + a_y$ coins for it.

What is the minimum number of coins you have to spend to make the graph connected? Recall that a graph is connected if it's possible to get from any vertex to any other vertex using only the edges belonging to this graph.

给你一个包含 $n$ 个顶点的无向图。每个顶点上写有一个数字；顶点 $i$ 上的数字为 $a_i$。初始时图中没有边。

你可以向该图中添加若干条边，但需要为此付费。在顶点 $x$ 和 $y$ 之间添加一条边的费用为 $a_x + a_y$ 枚硬币。此外还有 $m$ 个特殊优惠，每个优惠用三个数 $x$、$y$ 和 $w$ 表示，含义是：你可以在顶点 $x$ 和 $y$ 之间添加一条边，并仅需支付 $w$ 枚硬币。你并非必须使用这些特殊优惠：即使顶点对 $x$ 和 $y$ 存在对应的特殊优惠，你仍可以选择按常规方式连接它们，即支付 $a_x + a_y$ 枚硬币。

为使该图连通，你至少需要花费多少枚硬币？注意，一个图被称为连通图，当且仅当图中任意两个顶点之间均存在仅由该图中的边构成的路径。

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — the number of vertices in the graph and the number of special offers, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$) — the numbers written on the vertices.

Then $m$ lines follow, each containing three integers $x$, $y$ and $w$ ($1 \le x, y \le n$, $1 \le w \le 10^{12}$, $x \ne y$) denoting a special offer: you may add an edge connecting vertex $x$ and vertex $y$, and this edge will cost $w$ coins.

第一行包含两个整数 $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$），表示一项特殊优惠：你可以添加一条连接顶点 $x$ 和顶点 $y$ 的边，该边的花费为 $w$ 枚金币。

Print one integer — the minimum number of coins you have to pay to make the graph connected.

输出一个整数——使图连通所需支付的最少硬币数量。

In the first example it is possible to connect $1$ to $2$ using special offer $2$, and then $1$ to $3$ without using any offers.

In next two examples the optimal answer may be achieved without using special offers.

在第一个例子中，可以使用特价优惠 2 将节点 $1$ 与节点 $2$ 连接，然后不使用任何优惠即可将节点 $1$ 与节点 $3$ 连接。

在接下来的两个例子中，最优解可在不使用任何特价优惠的情况下达成。