Make It Connected
Contest: Codeforces Round 529 (Div. 3)
Difficulty rating: 1900
Tags: dsu, graphs, greedy

You are given an undirected graph consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is $$$a_i$$$. Initially there are no edges in the graph.

You may add some edges to this graph, but you have to pay for them. The cost of adding an edge between vertices $$$x$$$ and $$$y$$$ is $$$a_x + a_y$$$ coins. There are also $$$m$$$ special offers, each of them is denoted by three numbers $$$x$$$, $$$y$$$ and $$$w$$$, and means that you can add an edge connecting vertices $$$x$$$ and $$$y$$$ and pay $$$w$$$ coins for it. You don't have to use special offers: if there is a pair of vertices $$$x$$$ and $$$y$$$ that has a special offer associated with it, you still may connect these two vertices paying $$$a_x + a_y$$$ coins for it.

What is the minimum number of coins you have to spend to make the graph connected? Recall that a graph is connected if it's possible to get from any vertex to any other vertex using only the edges belonging to this graph.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — the number of vertices in the graph and the number of special offers, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — the numbers written on the vertices.

Then $$$m$$$ lines follow, each containing three integers $$$x$$$, $$$y$$$ and $$$w$$$ ($$$1 \le x, y \le n$$$, $$$1 \le w \le 10^{12}$$$, $$$x \ne y$$$) denoting a special offer: you may add an edge connecting vertex $$$x$$$ and vertex $$$y$$$, and this edge will cost $$$w$$$ coins.

Output format:
Print one integer — the minimum number of coins you have to pay to make the graph connected.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example it is possible to connect $$$1$$$ to $$$2$$$ using special offer $$$2$$$, and then $$$1$$$ to $$$3$$$ without using any offers.

In next two examples the optimal answer may be achieved without using special offers.

Example input:
3 2
1 3 3
2 3 5
2 1 1

Example output:
5

Example input:
4 0
1 3 3 7

Example output:
16

Editorial:
Suppose we have found all the edges of the graph explicitly, sorted them, and start running Kruskal on the sorted list of edges. Each time we add some edge to MST, it is either a special edge given in the input, or an edge which was generated with cost $$$a_x + a_y$$$ (whichever costs less). Let's try to analyze how can we find the cheapest edge of each type that connects two components. For special edges, we may just maintain the number of special edges we already added or skipped, and when choosing a new edge, we skip some more (possibly zero) special edges that don't connect anything, until we find an edge that connects something. And for the other type of edges, we may find two components having minimum numbers on the vertices in those components as small as possible, and just connect the minimum vertex in the first component with the minimum vertex in the second component. We may simulate this by maintaining a data structure (for example, a multiset), where for each component we will store the vertex having minimum $$$a_i$$$ in this component, and pick two minimums from this set. We also have to be able to check if two vertices are connected (this can be done with DSU) and merge two components.
But this solution can be made easier. Every time we add a "non-special" edge, one of the ends of this edge is the vertex with minimum $$$a_i$$$. So we may just find this vertex, generate all edges connecting this vertex to all other vertices, merge this set of edges with the set of special edges, and run any MST algorithm on the resulting set of edges. If there are multiple minimums in the array $$$a$$$, then we may pick any of them because in Kruskal algorithm it doesn't matter which of the edges with equal costs we try to add first.