simcity

Problem Description

Peanut is building a new city in SimCity! His city consists of N towns, each initially disconnected from one another. Peanut wants to build roads between the towns and airports within the towns such that every town which does not contain an airport must be connected by road directly or indirectly to a town with an airport. There are R proposed roads that Peanut can build, and the ith road will connect towns A_i and B_i, and costs C_i dollars to build.

At first, no town in the city has an airport. Building an airport in city i will incur a cost of D_i dollars. Help Peanut determine the minimum cost incurred in constructing such a city.

Input

The first line of input will contain two integers, N and R.

The second line of input will contain N integers, representing the array D.

The next R lines of input will contain three integers each, A_i, B_i and C_i.

Output

The first and only line of input should contain one integer, the minimum cost incurred to build such a city.

Limits

For all subtasks: 0 ≤ A_i, B_i < N, 0 ≤ C_i, D_i ≤ 10⁹.

Subtask 1 (20%): 1 ≤ N, R ≤ 1000.

Subtask 2 (22%): 1 ≤ N, R ≤ 300000, C_i = 0.

Subtask 3 (23%): 1 ≤ N, R ≤ 300000, D_i = 10⁹.

Subtask 4 (35%): 1 ≤ N, R ≤ 300000.

Subtask 5 (0%): Sample Testcases.

Sample Input 1

4 4
1 2 3 4
0 1 2
1 2 1
2 0 1
2 3 5

Sample Output 1

7