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 Ai and Bi, and costs Ci dollars to build.

At first, no town in the city has an airport. Building an airport in city i will incur a cost of Di 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, Ai, Bi and Ci.

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 ≤ Ai, Bi < N, 0 ≤ Ci, Di ≤ 109.

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

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

Subtask 3 (23%): 1 ≤ N, R ≤ 300000, Di = 109.

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

Submitting .cpp to 'simcity'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 25
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 20
2 22
3 23
4 35
5 0