Make It Connected

Description:

Input:

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.

Output:

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

Sample Input:

3 2
1 3 3
2 3 5
2 1 1

Sample Output:

5

Sample Input:

4 0
1 3 3 7

Sample Output:

16

Sample Input:

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

Sample Output:

18

Note:

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.