CF1095F Make It Connected

Statement

Vertex i has value a_i. Any two different vertices x,y may be connected for a_x+a_y. There are also m optional special offers connecting specified endpoints for cost w. Find the minimum total cost needed to make the graph connected.

Input

The first line contains n,m (1 <= n <= 200000, 0 <= m <= 200000). The second line contains a_i (1 <= a_i <= 10^12). Each of the next m lines contains x,y,w, where x != y and 1 <= w <= 10^12.

Output

Print the minimum total cost required to make the graph connected.

Example

3 2
1 3 5
1 2 2
2 3 1

3