Sparkle is a king whose domain has fallen into disrepair and ruin, following a series of wars and natural disasters. He used to rule the world, then his world began to fall. His kingdom consists of numerous villages, which are connected by bidirectional roads. However, the roads are now all ruined, and will require a certain cost each to repair.

During the period of conflict, the technology to create portals was discovered. Sparkle can pay to repair roads connecting villages, or he can pay to install portals at any village. Any village with a portal is instantly linked with all other villages with portals. Additionally, Sparkle wants to show off his superior technology, so at least one portal must be constructed. Can you help find the minimum cost to ensure that any village can reach any other village through roads and portals while constructing at least one portal?

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n \leq 10^5, 0\leq m \leq 10^5)~, the number of villages and the number of roads. The villages are labelled ~1~ through ~n~.

The next line contains ~n~ space-separated integers ~a_i~ ~(1 \leq a_i \leq 10^4)~, the cost to build a portal at each of the ~n~ villages. All villages that have built portals are connected to each other.

The next ~m~ lines each contain the information about the roads as ~u_i~, ~v_i~ and ~c_i~ ~(1 \leq u_i,v_i \leq n, u_i \neq v_i, 1 \leq c_i \leq 10^4)~. The integers ~u_j~ and ~v_j~ represent the endpoints of the road, and ~c_j~ represents the cost to repair the road. All roads are bidirectional, and there may be multiple edges between the same pair of villages.

Output

Output the minimum cost to make all the villages be able to reach all the other villages by traversing roads and portals while constructing at least one portal.

Example

Input 1

4 2
5 4 3 10
1 2 6
3 4 7

Output 1

19

The best option here is to build portals at villages ~1~, ~2~, and ~3~, and then connect ~3~ and ~4~ via road. The portals have cost of ~5+4+3=12~, and the road has cost ~7~. This is the cheapest option.

Input 2

3 3
7 2 6
1 2 3
2 3 4
1 3 10

Output 2

9

The best option here is to just rebuild the roads ~1-2~ and ~2-3~ for total cost ~7~. This connects the villages, but you must additionally build at least one portal, so the portal at village ~2~ is constructed for ~2~ more cost.

Input 3

5 0
8 6 4 9 5

Output 3

32

Here there are no roads, so the only option is rebuild every single portal.