Problem Description

Takahashi is managing a country in a game.

The country has $ N $ cities and $ M $ roads. Each road directly connects two different cities, and there are no other cities on the road. Also, for any two cities, there is at most one road directly connecting them.

Initially, none of the roads are paved, and no city has a marketplace installed.

Takahashi decided to pave the roads and install marketplaces for the development of the country.

A country is considered to be in a "good state" if, for every city, one of the following conditions is met:

• The city has a marketplace installed.
• The city does not have a marketplace installed, but it can reach another city with a marketplace installed via only paved roads.

Cities are numbered from $ 1 $ to $ N $, and roads are numbered from $ 1 $ to $ M $. Installing a marketplace in city $ i $ requires $ c_i $ gold coins. Paving road $ i $ requires $ r_i $ gold coins.

Since Takahashi does not have many gold coins, he wants to minimize the number of gold coins needed to bring the country to a "good state".

Write a program to find the minimum number of gold coins required.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ c_1 $ $ c_2 $ : $ c_N $ $ a_1 $ $ b_1 $ $ r_1 $ $ a_2 $ $ b_2 $ $ r_2 $ : $ a_M $ $ b_M $ $ r_M $

• The first line contains two integers $N\ (2\ ≦\ N\ ≦\ 100,000)$ and $M\ (1\ ≦\ M\ ≦\ 200,000)$, indicating the number of cities and roads, respectively.
• The next $ N $ lines contain an integer $c_i\ (1\ ≦\ c_i\ ≦\ 1,000,000,000)$, representing the number of gold coins required to install a marketplace in city $ i $.
• The next $ M $ lines contain three integers $ a_i $, $b_i\ (1\ ≦\ a_i\ ＜\ b_i\ ≦\ N)$, and $r_i\ (1\ ≦\ r_i\ ≦\ 1,000,000,000)$, indicating that road $ i $ connects city $ a_i $ and city $ b_i $ and costs $ r_i $ gold coins to pave.

Output Format

Output the minimum total cost in gold coins required to bring the country to a "good state" in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

Sample Output #1

350

Sample Input #2

3 3
50
50
50
1 2 60
1 3 60
2 3 60

Sample Output #2

150

Sample Input #3

5 7
80
70
60
50
40
1 3 20
1 4 70
1 5 30
2 3 30
2 4 90
3 4 40
4 5 80

Sample Output #3

160

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N\ ≦\ 8$ and $M\ ≦\ 10$, you will get $ 10 $ points.
• If you solve the dataset where $N\ ≦\ 12$ and $M\ ≦\ 66$, you will get an additional $ 20 $ points.
• If you solve the dataset where $N\ ≦\ 3,000$ and $M\ ≦\ 6,000$, you will get an additional $ 30 $ points.
• If you solve the dataset without additional constraints, you will get an additional $ 40 $ points.

见题面 Input 部分

见题面 Output 部分