VERY IMPORTANT NOTE TO ALL DEC COURSE 2022 PARTICIPANTS (due to delays in email communication): Elementary is gone, so Advanced has a diagnostic test (if you fail, no Dec Course). Syllabus of diagnostic is anything in these prerequisite notes, please review them at this link. Problemsets can be found at this link and under Contests (Collections).

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 *i*th road will connect towns *A _{i}* and

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.

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}*,

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

For all subtasks: 0 ≤ A_{i}, B_{i} < N, 0 ≤ C_{i}, D_{i} ≤ 10^{9}.

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^{9}.

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

Subtask 5 (0%): Sample Testcases.

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

7

Subtask | Score |
---|---|

1 | 20 |

2 | 22 |

3 | 23 |

4 | 35 |

5 | 0 |