#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

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

*B*, and costs

_{i}*C*dollars to build.

_{i}
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*and

_{i}*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^{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.

## 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 20 | 21 | 1s | 256MB | Minimum |

2 | 22 | 20 | 1s | 256MB | Minimum |

3 | 23 | 20 | 1s | 256MB | Minimum |

4 | 35 | 81 | 1s | 256MB | Minimum |

5 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o simcity -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512