C. Global Resupply
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Logistics is the lifeblood of war...

In a vast strategic buffer zone, there are $$$n$$$ frontline outposts, indexed from $$$1$$$ to $$$n$$$. Due to the intensity of the battle, the headquarters commands that every single outpost must receive supplies.

As the logistics commander, you have two methods to provide supplies to the outposts:

  1. Direct Airdrop: You can choose to establish an airdrop station at any outpost $$$i$$$. The cost to airdrop supplies to outpost $$$i$$$ is $$$a_i$$$. Once an airdrop station is established, that outpost is considered supplied.

  2. Land Transport: There are $$$m$$$ potential bidirectional supply roads. The $$$j$$$-th road connects outpost $$$u_j$$$ and outpost $$$v_j$$$ with a construction cost of $$$w_j$$$. If a road is built between two outposts, and one of them is already supplied (either via airdrop or transport from another outpost), the other outpost also becomes supplied.

Your goal is to formulate a plan with the minimum total cost such that all $$$n$$$ outposts are supplied.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \times 10^5$$$, $$$0 \le m \le 2 \times 10^5$$$), representing the number of outposts and the number of potential roads.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the cost of directly airdropping supplies to the $$$i$$$-th outpost.

The following $$$m$$$ lines each contain three integers $$$u, v, w$$$ ($$$1 \le u, v \le n$$$, $$$1 \le w \le 10^9$$$), representing a potential bidirectional road between outpost $$$u$$$ and outpost $$$v$$$ with a cost of $$$w$$$.

Note: The input may contain self-loops or multiple edges between the same pair of outposts.

Output

Output a single integer representing the minimum total cost required to supply all outposts.

Example
Input
3 2
5 10 3
1 2 1
2 3 2
Output
6
Note

In the sample case, the optimal strategy is:

  1. Establish an airdrop station at Outpost 3 (Cost: $$$3$$$). Outpost 3 is now supplied.
  2. Build the road between Outpost 3 and Outpost 2 (Cost: $$$2$$$). Supplies are transported from 3 to 2. Outpost 2 is now supplied.
  3. Build the road between Outpost 2 and Outpost 1 (Cost: $$$1$$$). Supplies are transported from 2 to 1. Outpost 1 is now supplied.
The total cost is $$$3 + 2 + 1 = 6$$$.