Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You are given an undirected graph consisting of n vertices. A number is written on each…

  1. User

    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

    The first line contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ m ≤ 2 ⋅ 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, ..., a_n (1 ≤ a_i ≤ 10^{12}) — the numbers written on the vertices.

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

    Output

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

    Examples

    Input

    3 2 1 3 3 2 3 5 2 1 1

    Output

    5

    Input

    4 0 1 3 3 7

    Output

    16

    Input

    5 4 1 2 3 4 5 1 2 8 1 3 10 1 4 7 1 5 15

    Output

    18

    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.

  2. DeepSeek Assistant

    We need to read problem: given n vertices with weights a_i. Cost to add edge between x and y is a_x + a_y. Also there are m special offers: (x, y, w) where we can add edge at cost w (which might be cheaper than a_x + a_y). We need to make graph connected by adding edges, with minimal total cost.

    We can add any edges we want, but each edge addition we choose either the standard cost or a special offer if exists (we can choose cheaper). Equivalent: we have a complete graph potential edges, but each edge has a cost: for each pair (x,y), cost = min(a_x + a_y, w_{xy}) where w_{xy} is the special offer if any (otherwise a_x+a_y). The goal: find a minimum spanning tree (MST) on this complete graph with n up to 200k, m up to 200k.

    But complete graph edges are too many (n choose 2). However note that the standard cost is a_x + a_y. This type of graph is similar to one where we can connect any vertex to the cheapest one? Actually there is a well-known trick: For a graph where each edge cost between i and j is a_i + a_j, the MST is achieved by connecting all vertices to the vertex with minimal a_i (since that forms a star with total cost (n-1)*min_a + sum_{others} a_i). Because for any two vertices i and j, a_i + a_j <=? Actually consider MST of a complete graph with edge cost = a_i + a_j: The MST is indeed a star centered at the vertex with smallest a. Proof: Prim's algorithm starting from smallest vertex: each addition cost = a_min + a_other. That yields total = (n-1)*a_min + sum_{i != min} a_i = sum all a_i + (n-2)*a_min? Wait compute: sum_{others} (a_min + a_i) = (n-1)a_min + sum_{others} a_i = (n-1)a_min + (total_sum - a_min) = total_sum + (n-2)a_min. But maybe there is cheaper? Check triangle inequality: a_i + a_j <= (a_i + a_min) + (a_min + a_j) = 2a_min + a_i + a_j, so star is not necessarily cheaper than direct connection? Actually compare star edges vs direct: connecting i to j directly costs a_i + a_j; connecting i to min and min to j costs (a_i + a_min) + (a_min + a_j) = a_i + a_j + 2a_min. So star adds extra 2a_min. So star is more expensive than direct connection. So MST might actually be connecting all to min? Let's check with small n: n=3, a=[1, 100, 100]. Direct edges: costs: 1+100=101, 1+100=101, 100+100=200. MST would pick the two edges of cost 101: total 202. Star: edges from min to both others: 101+101=202, same. So star is MST. Another example: a=[1,2,3]. Direct: 1+2=3, 1+3=4, 2+3=5. MST picks 3 and 4 = 7. Star: 1-2(3) and 1-3(4) total 7. So star seems optimal. But can there be a case where MST uses a direct edge between two non-min vertices rather than both connecting to min? Suppose a=[2,3,4]. Star: 2-3 (5) and 2-4 (6) total 11. Direct MST: 2-3 (5), 3-4 (7) total 12. So star is better. Actually star yields 11, direct gives 12. So star is optimal. So indeed for complete graph with cost = a_i + a_j, the MST is a star centered at the vertex with minimal a_i. Reason: Consider any spanning tree T. The sum of costs = sum_{edges (i,j)} (a_i + a_j) = (n-1) * sum_{vertices} (degree(v) * a_v?) Actually each vertex v appears in degree(v) edges, so total cost = sum_v a_v * deg(v). Since sum of degrees = 2(n-1). So total = sum_v a_v * deg(v). To minimize this, we want to assign higher degree to vertices with smaller a_v. The star gives degree n-1 to min, degree 1 to others. That's optimal because we allocate as much degree as possible to the smallest a. More formally, it's a linear programming: minimize sum a_v d_v subject to sum d_v = 2(n-1), 1 <= d_v <= n-1 (but degree constraints also need to be realizable as a tree? However any nonnegative integer degrees with sum = 2(n-1) and each >=1 can be realized as a tree (if graph is connected, degrees must be >=1). The minimal sum is achieved by setting the smallest a_v to have d_v = n-1, others d_v = 1. Because we want to maximize degree on smallest. So indeed MST cost = (n-1)*min_a + sum_{others} a_i = total_sum + (n-2)*min_a? Actually sum others = total_sum - min_a, so total = (n-1)*min_a + (total_sum - min_a) = total_sum + (n-2)*min_a. Wait check: total_sum = min_a + sum_others. So (n-1)*min_a + sum_others = (n-1)*min_a + total_sum - min_a = total_sum + (n-2)*min_a. Yes.

    Thus the base MST cost if we only use standard edges is total_sum + (n-2)*min_a.

    But we also have special offers that may reduce cost.

    Now we need to compute MST on n vertices with edge costs defined as: for each pair (i,j), cost = min(a_i + a_j, w_{ij}) where w_{ij} is the special offer if present (otherwise a_i+a_j). Since m is up to 200k, we cannot consider all pairs.

    Observation: The standard cost a_i + a_j is like a universal fallback. The MST could be constructed by considering two types of edges: the special offers (each with its own weight), and the "cheap" edges from each vertex to the vertex with minimal a (or perhaps to the minimal vertex for each vertex). But maybe more clever: we can think of adding an extra "virtual" vertex representing the base cost? Another approach: Transform the problem into a graph with n + 1 vertices? Known trick: For problems where edge cost between i and j is min(a_i + a_j, w_{ij}), the MST can be found by constructing a graph with an additional node 0 connected to each vertex i with cost a_i. Then for each special offer (i,j,w), add an edge between i and j with cost w. Then the MST of this (n+1)-node graph, when we remove the connections to node 0 (if any), gives the MST of original? Need to verify.

    Consider: Suppose we have a complete graph with cost c(i,j)=min(a_i+a_j, w_{ij}). Build an auxiliary graph with nodes 1..n and an extra node 0. Connect node 0 to each i with weight a_i. Also for each special offer (i,j,w), add edge i-j with weight w. Now consider any spanning tree of the original graph (only nodes 1..n). How does it relate to a spanning tree of the auxiliary graph that includes node 0? If we take a spanning tree T on original, we can add edge from some vertex i to node 0 with weight a_i to get a spanning tree of the augmented graph (since adding node 0). The total weight would be total(T) + a_i. Conversely, any spanning tree of the augmented graph that includes node 0, when we remove node 0, gives a spanning forest of the original nodes (maybe a tree? Actually if the tree connects all n+1 nodes, removing node 0 yields a spanning forest that might be connected? It could be disconnected because node 0 could have degree 1, then removing it yields a connected graph on n nodes. But if node 0 has degree >1, then after removal the original nodes become disconnected? Let's think: If the tree on n+1 nodes is spanning, it connects all nodes. If we remove node 0, the remaining graph is what's left after deleting that node and its incident edges. If node 0 had degree d, then removing it creates d separate components (since tree: removing a node splits the tree into d connected components, each attached via one edge). So the result is a forest with d components. To get a spanning tree on original nodes (connected), we need d=1 (node 0 leaf). So not every spanning tree of augmented graph corresponds to a connected spanning tree on original nodes.

    But maybe the MST of the original graph can be found by computing MST of the augmented graph (including node 0) and then discarding node 0? However MST of augmented graph will likely connect node 0 to many vertices, resulting in d>1, so removal yields disconnected forest. That's not valid.

    Alternate well-known technique: For problems where edge cost is min( a_i + a_j, w_ij ), you can consider each vertex connecting to the minimal vertex as standard. Actually we can treat the standard edges as: we could connect any pair for cost a_i + a_j, but that's like having a complete graph with those costs. Since MST of a complete graph with those costs is the star centered at min vertex, we can include those n-1 edges as candidate edges: for each vertex i != min_index, add an edge (min_index, i) with cost a_min + a_i. However, is it sufficient to only consider these n-1 standard edges plus all special offers? Might the MST use a standard edge that is not to the min vertex? Suppose we have special offers that are cheap, and the MST may consist of some special edges and some standard edges. Could it ever be optimal to use a standard edge between two non-min vertices? Possibly if the min vertex is already connected via some path, and adding an edge between two other vertices is cheaper than connecting one of them to min? But standard cost for two non-min vertices is a_i + a_j, which is at least a_min + a_i (since a_j >= a_min) and also at least a_min + a_j. Actually compare a_i + a_j vs a_min + a_i: a_i + a_j - (a_min + a_i) = a_j - a_min >= 0. So a_i + a_j >= a_min + a_i. Similarly, it is >= a_min + a_j. So connecting either to min is cheaper or equal. So if we need to connect a component containing min to another component, the cheapest way using standard edges is to connect some vertex in that component to min (if min is in the component) or connect min to the other? Actually if min is in component A, and we want to connect component B, the cheapest standard edge between A and B is to take the vertex with minimal a in A and minimal a in B? But since min is in A, the edge from min to any vertex in B costs a_min + a_j, which is <= a_i + a_j for any i in A, because a_i >= a_min. So yes, the cheapest standard edge connecting A and B is to use the min vertex (if in A) and some vertex in B. So in the MST algorithm (Kruskal) we only need to consider standard edges that involve the global minimum vertex. Because any other standard edge is dominated: for any pair (i,j) where i != min and j != min, the cost a_i + a_j is >= a_min + a_i and also >= a_min + a_j. So if we have the option to use edges (min, i) and (min, j) at those costs, perhaps we don't need i-j directly. However, the MST might include i-j if both i and j are already connected to min via other edges? But Kruskal sorts edges, and if cheaper edges are available, they will be taken first. Typically, in MST, if we have edges (min,i) and (min,j) with costs a_min + a_i and a_min + a_j, both are cheaper than a_i + a_j unless a_min is large? Actually since a_min is the smallest, a_min + a_i <= a_i + a_j because a_min <= a_j. So (min,i) is cheaper than (i,j). Similarly (min,j) cheaper. So in Kruskal's order, edges (min,i) and (min,j) would come before (i,j) (since sorted by weight). So if we consider all edges, it's likely that MST would pick those edges before considering i-j. However, we might not pick both (min,i) and (min,j) if they would create a cycle, but still the MST would have some edges connecting min to others. Could there be a scenario where MST does not include min vertex as a leaf? Actually min vertex will definitely be included, but might not be connected directly to every other vertex; some vertices might connect to others if that yields lower total cost when combined with special offers. But the standard edges we consider are only from min to others, which are the cheapest possible standard edges for any pair involving min. For a non-min vertex i, the cheapest standard edge to any other vertex is to min (since a_min + a_i <= a_i + a_j for any j != i). So if i needs to be connected via standard edges, the best is to connect to min. So it's safe to only consider standard edges from min to all other vertices as candidates, because any other standard edge is not needed: if MST uses a standard edge between i and j, we could replace it with the edge (min, i) or (min, j) (if not creating cycle) without increasing cost? But careful: In the MST, if there is already a path between min and i (maybe through special offers), then adding edge (min,i) might create a cycle. However, we might replace the i-j edge with some other edge to maintain connectivity. The classic approach for problems with edge cost = a_i + a_j often reduces the candidate edges to n-1 edges from min to others, because the MST of the complete graph with that cost is exactly that star. But here we also have special offers that might be cheaper than those star edges. So overall, we can consider the graph G' that has:

    • For each special offer (x,y,w), an edge between x and y with weight w.
    • For each vertex i (i != min_idx), an edge between min_idx and i with weight a_min + a_i.

    And then compute MST on this graph with n vertices and (m + n-1) edges. Since n up to 2e5, m up to 2e5, total edges ~ 4e5, MST via Kruskal (sort) is feasible. But is this sufficient? Need to ensure that any MST of the original complete graph with costs = min(a_i+a_j, w_ij) can be formed using only these edges. Essentially, we need to prove that there exists an MST that uses only special offer edges and standard edges from the global minimum vertex. Because if an MST uses a standard edge that does not involve the min vertex, we could replace it with something not more expensive.

    Let's attempt proof:

    Let v0 be vertex with minimal a (call it v0). Consider any spanning tree T of original graph (with costs c(i,j) = min(a_i+a_j, w_ij)). We will transform T into a spanning tree T' that uses only edges of types: special offers, or edges from v0 to other vertices, without increasing total cost.

    Consider any edge e = (u,v) in T that is a standard edge (i.e., c(u,v) = a_u + a_v) and suppose neither u nor v is v0 (if one is v0, it's already of desired type). We'll try to replace e with another edge that maintains connectivity and is not more expensive.

    Since T is a tree, removing e splits T into two components. Let component containing v0 be A, and the other be B. Without loss, assume v0 in A. Then u and v are in different components? Actually e connects u and v, and since v0 in A, one of u,v is in A and the other in B? Possibly both not in A? But v0 is in A, so if neither u nor v is v0, it's possible that both u and v are in the same component relative to v0? Wait: If we remove e, the tree splits into two components. Since v0 is somewhere, it will be in exactly one of these components. The other component does not contain v0. So exactly one of u,v is in the component containing v0? Not necessarily: The edge e is between u and v, so after removal, u and v are in different components. So one component contains u, the other contains v. Since v0 is in exactly one component, it's either with u or with v. So one of u,v is in same component as v0; the other is not. So w.l.o.g., assume u in component with v0 (A), and v in component B (without v0).

    Now, consider the standard edge between v0 and v: cost = a_v0 + a_v. Since v0 has minimal a, a_v0 + a_v <= a_u + a_v (because a_u >= a_v0). So we have c(v0, v) <= a_u + a_v = c(u,v) (if c(u,v) = a_u + a_v). However, note that there might be a special offer for (v0, v) that could be even cheaper, but our candidate edge includes either the special offer or the standard cost via v0. In any case, we can consider the edge (v0, v) with cost = min(a_v0 + a_v, w_{v0,v}) which is <= a_v0 + a_v. Since we are allowed to use either, but in our candidate set we have the edge between v0 and v with weight min(...). Actually we need to be careful: The candidate set we proposed includes edges from v0 to i with weight a_v0 + a_i. But if there is a special offer between v0 and i with weight w < a_v0 + a_i, then that special offer would be included as a separate edge (since we include all special offers, including those involving v0). So the cheapest edge between v0 and i is min(a_v0 + a_i, w). In our candidate set, we have: for each i != v0, an edge (v0,i) with weight a_v0 + a_i. But also if there is a special offer (v0,i,w), it will also be present with weight w. However, if w < a_v0 + a_i, then the edge (v0,i) with weight w will be in the special offers list and the edge (v0,i) with weight a_v0 + a_i is also present, but that's okay; we have both. But note that the edge (v0,i) with weight a_v0 + a_i might be dominated by the special offer, but it's still present. However, in our candidate set, we might have duplicate edges (same pair) with different weights, but that's fine; MST algorithm will pick the cheaper when sorting.

    Now, consider replacing edge (u,v) with edge (v0, v). Since after removal of (u,v), v0 and v are in different components (v0 in A, v in B), adding (v0, v) would reconnect the tree. The cost of (v0,v) is <= a_u + a_v. So we can replace e with (v0,v) without increasing total cost. However, we must ensure that (v0,v) is present in our candidate set? In the transformed tree, we may have introduced an edge that is not in our candidate set if it's a special offer? Actually (v0,v) is definitely either a standard edge (v0,v) with cost a_v0 + a_v, or if there is a special offer, it's even cheaper; but in both cases, that edge is present either as a special offer (if exists) or as the standard edge (v0,v) we explicitly included. So it's in the edge set. So we can replace.

    By iteratively replacing any standard edge that does not involve v0, we can obtain a spanning tree that uses only edges incident to v0 (standard or special) and special offers between non-v0 vertices. But does it guarantee that all standard edges are incident to v0? Yes, after replacement, any standard edge is either (v0,i) or has been replaced. However, we might also have edges that are special offers, which can be between any vertices. So final tree T' contains only edges that are either special offers (any pair) or standard edges of the form (v0,i). That matches our candidate set: we have all special offers, and all standard edges from v0 to others. So any MST can be transformed into a tree that only uses these edges without increasing cost. Therefore, the MST of the original complete graph is the same as the MST of the graph consisting of these edges. So we can safely restrict to that graph.

    One nuance: The replacement might introduce cycles if we add (v0,v) while keeping (v0,u) etc., but we are constructing a new tree: we remove (u,v) and add (v0,v), so the resulting graph is still a spanning tree (since we remove one edge from cycle? Actually we remove e from tree, get two components; then add edge connecting the two components, yielding a tree again). So it's valid.

    Thus solution: Let min_index = argmin a_i (if multiple, any). Let min_a = a[min_index].

    Construct edges list:

    • For each special offer (x, y, w), add edge (x, y, w).
    • For each i from 1 to n, if i != min_index, add edge (min_index, i, min_a + a_i).

    Then run MST (Kruskal) on n vertices with these edges.

    But wait: Is it possible that the MST uses a standard edge (min_index, i) even if there is a cheaper special offer between min_index and i? That's fine because we have both, and the cheaper one will be considered first.

    Edge count: m + (n-1) <= 4e5, which is fine.

    However, we must consider that special offers may also be for pairs where the standard cost is cheaper than w? But we include them anyway; we trust MST to pick min.

    Now we need to confirm with examples.

    Example1: n=3, a=[1,3,3] (a1=1, a2=3, a3=3). min_index=1, min_a=1. Edges: standard: (1,2) cost 1+3=4; (1,3) cost 1+3=4. Special offers: (2,3,5); (2,1,1) [note second special: 2 1 1]. That is (1,2) with cost 1, which is cheaper than 4. So edges: (1,2,1), (2,3,5), (1,2,4) (but duplicate, but sorted will pick 1 first), (1,3,4). MST: pick (1,2) cost 1, then among remaining cheapest connecting: (1,3) cost 4 (since (1,3) 4, (2,3) 5). Total 5. Matches output.

    Example2: n=4, a=[1,3,3,7], m=0. min_index=1 (a=1). edges: (1,2) 1+3=4, (1,3) 4, (1,4) 8. MST picks all three: 4+4+8=16. Output 16. OK.

    Example3: n=5, a=[1,2,3,4,5]; min_index=1, min_a=1. standard edges: (1,2) cost 3, (1,3) 4, (1,4) 5, (1,5) 6. Special offers: (1,2,8) (ignore since cheaper standard 3), (1,3,10) ignore, (1,4,7) >5 so ignore, (1,5,15) ignore. So effectively only standard edges considered? Wait also offers are only from 1 to others, but we already have those edges. So MST would be all standard: total = 3+4+5+6=18. Output 18. matches.

    But note: There might be offers between non-min vertices that are cheaper than connecting both to min. For instance, suppose a = [100, 1, 2], but min is 1 at vertex2? Actually min =1 at vertex2. Then standard edges from min: (2,1) cost 1+100=101, (2,3) cost 1+2=3. Suppose there is a special offer (1,3) with w=50. Then standard edges from min: (2,1)=101, (2,3)=3. With MST: we might take (2,3)=3, then need to connect vertex1. Options: (1,2)=101, (1,3)=50 (special). MST would take (1,3)=50, total 53. That's fine because we have special offer (1,3) included. So works.

    Now, what about special offers that are even cheaper than a_min + a_i? Example: a=[10, 10, 10], min=10 (any). Standard edges: all cost 20. Suppose special offer (2,3) w=5. Then edges: standard from min (say vertex1) to 2 (20), to 3 (20); plus special (2,3,5). MST: pick (2,3) 5, then need to connect component {2,3} to {1}. Cheapest edge between them: (1,2)=20 or (1,3)=20. Total 25. Is that optimal? Could there be a tree with two edges both special? But there is only one special offer. So optimal 25. Our graph includes all needed.

    Edge case: multiple vertices with same minimal a. The transformation still works: pick any one as v0. But consider if there are multiple minima, maybe we can connect them with cost 2a_min (which equals a_min+a_min). That's the same as connecting to v0? Suppose we have two min vertices i and j, both have a_i = a_j = min. Standard edge between them: 2min. In our candidate set, we have edges from chosen v0 (say i) to j with cost min+min=2*min. So it's included. So fine.

    Now confirm correctness: We must ensure that the transformation does not miss the possibility of using a standard edge between two non-min vertices that is cheaper than any combination involving min? But we argued a_min + a_i <= a_i + a_j because a_min <= a_j. So indeed it's cheaper or equal. So it's safe.

    Thus solution is straightforward: compute MST on graph with edges: all special offers, plus n-1 edges from min index to others with cost a_min + a_i.

    But wait: What about special offers that are exactly for pairs that include min? They are already present, but we also add the standard edge from min to that vertex; that's fine.

    Complexities: n,m up to 2e5. Sorting edges O(E log E) where E = m + n-1 ≤ 4e5, fine. Use DSU.

    Potential pitfalls: a_i up to 1e12, so costs up to 2e12, fits in 64-bit. Use long long.

    Edge case: n=1. Then graph already connected (single vertex). Need to spend 0 coins. Our algorithm: if n=1, then m may be 0 or some? But n≥1. For n=1, we should output 0. In our edge construction: min_index = 1, we would add no standard edges (since n-1=0). DSU on 1 vertex with no edges: MST cost = 0. Works.

    Also m may be 0.

    Check if we need to consider possibility that using a standard edge not from the global min might be cheaper due to special offers? No, because standard edge cost is fixed regardless; we are not forced to use the min vertex if there is a special offer from a different vertex? But our candidate set includes only standard edges from min. Could there be a case where using a standard edge from a non-min vertex is cheaper than using the min vertex's standard edge? As argued, no because a_min + a_i <= a_j + a_i for any j (since a_min <= a_j). So standard edge from min is always cheaper or equal. Therefore, any MST would not use a standard edge from a non-min vertex because it can be replaced by an edge from min to the same vertex with lower or equal cost, while preserving connectivity? But need to ensure replacement doesn't create cycle. Suppose we have a tree where the min vertex is already connected via some path to vertex i, so adding edge (min, i) would create a cycle. But if the tree already contains a standard edge (j,i) where j != min, we might consider replacing (j,i) with (min,i) while removing something else. The earlier transformation argument covers this.

    Thus solution stands.

    But wait: The transformation argument considered replacing a standard edge (u,v) where neither is min, by edge (min,v) (if min and u in same component). However, it could be that both u and v are not in the component of min? That's impossible because the tree is connected; min is somewhere; after removal, exactly one of u or v is in min's component. So fine.

    Now verify with more complex scenario: Suppose the tree uses a standard edge between two vertices both of which are not min, but min is in a different part of tree. After removal, min's component may be the one containing neither u nor v? Actually, since min is connected to everything, it must be in one of the two components after removing (u,v). Because the tree is connected, min is somewhere; after removing edge, the tree splits into two components; min belongs to exactly one component. So one of u or v is in same component as min. So that case is covered.

    Thus algorithm.

    Now complexity O((n+m) log(n+m)). Good.

    Implementation steps:

    1. Read n, m.
    2. Read array a[1..n].
    3. Find min_index (the index of minimum a). Since a_i can be up to 1e12, but comparisons fine. If multiple minima, choose the first.
    4. Initialize vector edges.
    5. For each special offer: read x,y,w. Add edge (x, y, w). Also maybe store as undirected (add both? just store once with x,y).
    6. For i from 1 to n: if i != min_index: add edge (min_index, i, a[min_index] + a[i]).
    7. Sort edges by weight.
    8. Initialize DSU of size n.
    9. total = 0, edges_used = 0.
    10. Iterate over sorted edges:
      • if find(u) != find(v): union, total += w, edges_used++.
      • if edges_used == n-1: break.
    11. Output total.

    But be careful: The standard edge from min to i might be already present as a special offer with lower weight. That's fine because we have both, but if we also include the standard edge with higher weight, it might be processed later and won't affect MST if already connected. But we might have duplicate edges of same pair with different weights, but sorting ensures we process the cheaper first. However, if there is both a special offer (min,i, w) and the standard edge (min,i, a_min + a_i), we will have two edges. When processing, the cheaper one (the special if w < a_min + a_i) will be considered first; if it connects the components, then later the more expensive duplicate will be ignored because they are already connected. So fine.

    Edge case: If there are multiple special offers for same pair, we include all; MST will pick cheapest.

    Now consider if the MST can be formed without using any edge from min? Could that happen if special offers already connect all vertices, and min is included in that connectivity? Yes, then no standard edges needed. That's fine: Our candidate set includes special offers; MST will pick them.

    Now, is it always necessary to add edges from min to all others? Could we reduce further? For standard edges, we only need those from min, as argued.

    Thus final answer.

    However, double-check with a scenario where a_min is not unique and we pick one min, but maybe using edges between other mins might be cheaper? Actually, suppose we have two minima with value min_a. If we pick one as v0, we have edge (v0, other_min) with cost 2*min_a. That's same as the direct edge between the two minima. So fine.

    Now, check constraints: m up to 2e5, so edges up to 400k. Sorting 400k edges: okay.

    Now, one more thought: Could there be a scenario where the MST uses a standard edge from a non-min vertex to min but we didn't add it? We added edges from min to all others, so it's included.

    Thus solution correct.

    But the problem might be known: "Connect" from Codeforces? I recall problem "D. Misha and Forest"? Not sure. Anyway.

    Now, let's examine potential pitfalls: Since a_i up to 1e12, sum might exceed 64-bit? n up to 2e5, a_i up to 1e12, so sum could be up to 2e5 * 1e12 = 2e17, which is within 2^63 (9.22e18), so 64-bit signed (long long) can hold. However MST total could be larger? For standard edges: total sum + (n-2)min <= nmax_a + ... could be up to 2e5 * 1e12 = 2e17, plus something, still safe. So use long long.

    Implementation details: Use 0-based or 1-based indexing for DSU. We'll store vertices as 0..n-1 or 1..n. For ease, convert to 0-index.

    Pseudo:

    int n, m; vector a(n); int min_idx = 0; for i in 0..n-1: if a[i] < a[min_idx] then min_idx = i;

    vector<tuple<long long, int, int>> edges; // weight, u, v

    for each special offer: read x,y,w; x--; y--; edges.emplace_back(w, x, y);

    for i in 0..n-1: if i != min_idx: edges.emplace_back(a[min_idx] + a[i], min_idx, i);

    sort edges.begin(), edges.end());

    DSU dsu(n); long long ans = 0; int cnt = 0; for each e: if dsu.unite(u,v) then ans += w; cnt++; if cnt == n-1 break;

    print ans.

    Edge Cases: n=1: edges empty, cnt remains 0, ans 0, prints 0.

    Now verify with some custom tests:

    Test 1: n=2, a=[5,7], m=0. min_idx=0. edges: (0,1,12). MST cost=12. But standard MST cost formula: total_sum + (n-2)*min = 12 + (0)*5=12? Actually total_sum=12, min=5, (n-2)=0 => 12. So correct.

    Test 2: n=2, a=[5,7], m=1 offer (1,2,10). edges: special (0,1,10) and standard (0,1,12). MST picks 10, ans=10.

    Test 3: n=4, a=[10,20,30,40], m=2 offers: (2,3,25) and (3,4,35). Indices: 1-based; convert. min_idx=0 (10). standard edges: (0,1)=30, (0,2)=40, (0,3)=50. special: (1,2,25) and (2,3,35). Sorted: 25 (1-2), 30 (0-1), 35 (2-3), 40 (0-2), 50 (0-3). MST: pick 25 (1-2), then 30 (0-1) connects component {0,1,2}? Actually after 25, comps: {1,2} and {0}, {3}. 30 connects 0-1, merging {0} with {1,2} => comp {0,1,2}. Then need to connect 3: cheapest edge from comp to 3? options: (2,3)=35, (0,3)=50. Choose 35. total = 25+30+35=90. Is that optimal? Possibly other: use (0,3)=50 and (0,2)=40 and (1,2)=25? That would be 40+25+50=115, worse. Or (0,1)=30, (0,2)=40, (0,3)=50 total=120. So 90 seems best. Our algorithm yields that.

    But is there a chance that MST would use (2,3)=35 and (0,2)=40 and (1,2)=25? That's the same as our selection? Actually (0,2)=40 would be added after, but (0,2) connects 0 to 2, but 0 already connected to 2 via 0-1-2? Actually after 25 and 30, we have 0-1-2 connected, so adding (0,2) would create cycle. So MST picks only one of those.

    Thus algorithm works.

    Now we must confirm that the transformation argument holds for all cases. Actually, I recall known Codeforces problem "1196F" maybe? Not exactly. There's a problem "1087D - Minimum Diameter Tree"? Not. I recall a problem: "Connect" (CF 1132C?) Actually there is CF Round #169 (Div2) problem "D. Lazy Student"? No.

    Anyway, solution is typical.

    But let me think about potential oversight: The cost of standard edge is a_x + a_y. But we add only edges from min to others. But what if there is a standard edge between two non-min vertices that is cheaper than the sum of two edges both incident to min? Wait, we are not summing two edges; we are replacing one edge with another edge. For MST, we consider single edges. The standard edge (i,j) might be cheaper than the edge (min,i) plus (min,j) but that's irrelevant because we are not forced to use both (min,i) and (min,j) to connect i and j; they might be connected via other edges. The key is that in any MST, the number of edges is exactly n-1. If we have a standard edge between i and j, we could potentially replace it with the edge (min,i) if min is not already connected to i. But if min is already connected to i via other edges, adding (min,i) would create a cycle. However, we could replace (i,j) with (min,j) if min and j are in different components. In the transformation we argued that after removing (i,j), min and one endpoint are in the same component, so we can add edge from min to the other endpoint. This works.

    But consider scenario where after removing (i,j), min is in the same component as both u and v? Impossible because removal splits tree into two components, and min can only be in one of them. So it's fine.

    Now, what about edges that are not standard? Those are special offers, and we keep them all.

    Thus transformation holds.

    Now complexity fine.

    Now we need to be careful about reading input: m could be 0, then we still have edges from min.

    Now consider if we have multiple edges between same pair: sorting will handle.

    Now DSU: implement with path compression and union by size/rank.

    Now edge storage: using tuple of (weight, u, v). Sort by weight.

    Now, note: There might be up to 4e5 edges, sorting O(4e5 log 4e5) ~ 4e5 * 19 = 7.6e6, fine.

    Now answer.

    But wait: Is there a scenario where the MST of the reduced graph might be more expensive than the true MST? Let's try to construct a counterexample if the transformation is incomplete. Suppose we have vertices with values: a = [10, 100, 101, 102]. min = 10 at v1. Standard edges from v1 to others: costs: 110, 111, 112. Now suppose there are special offers: (v2, v3, 180) (which is less than a2+a3=201 but greater than 111? Actually 180 > 111? 111? Wait a2+a3 = 100+101=201, special 180 is cheaper than 201 but more than a1+a2=110 and a1+a3=111. So special offers might be between non-min vertices that are cheaper than connecting them directly via standard, but still more expensive than connecting each to min. But consider a special offer (v2, v4, 105) which is cheaper than a1+v4=112? Actually a1+v4=10+102=112, special 105 is cheaper than 112 but more than a1+v2=110? Actually 105 < 112, but >110? 105 < 110? 105 is less than 110? Actually 105 < 110, so it's cheaper than connecting v2 to min? That would be surprising: v2 to min cost 110, but v2 to v4 cost 105 via special. However, a2+a4 = 100+102=202, so special 105 is much cheaper. So this edge is cheaper than (min, v2). So it might be used in MST to connect v2 and v4 instead of using min. That's fine; it's a special offer, included.

    Now, consider if there is no special offer for (min, v4) but there is a special offer for (v2, v4) cheaper than (min, v4). Then MST might connect v4 via v2 rather than directly to min. That's covered.

    Now, what if there is a standard edge between v3 and v4 that is cheaper than the sum of (min, v3)+(min, v4)? But that's not relevant: we never need to consider (v3,v4) standard because if it's cheaper than both (min,v3) and (min,v4)? Actually standard (v3,v4) cost a3+a4 = 101+102=203, while (min,v3)=111, (min,v4)=112. So (v3,v4) is much more expensive. So no.

    Now, what if the min is not unique and we pick one, but perhaps the MST could use standard edges between two other minima and avoid using the one we picked as hub? For example, a = [1,1,100,100]. Two minima (1 and 2). If we pick v1 as min, we add edges (v1,v2) cost 2, (v1,v3) cost 101, (v1,v4) 101. Alternatively, MST could be: (v1,v2) cost 2, (v2,v3) cost 101? Actually (v2,v3)=1+100=101, (v2,v4)=101. So similar. But could we avoid using v1 altogether and use v2 as hub? That is symmetric. Our candidate set includes edges from v1 only. But if we pick v1, the edge (v2,v3) is not present unless it's a special offer. In the case of two minima, the MST might need an edge between v2 and v3. But our candidate set does not include standard edge (v2,v3). However, we have standard edge (v1,v3) and (v1,v2). To connect v3, we might use (v1,v3). But could there be a cheaper alternative using (v2,v3) instead of (v1,v3)? Since a1 = a2 = 1, both cost 1+100=101. So (v2,v3) also cost 101. But it's not in our edge set unless we add it. Is that a problem? Suppose MST without using v1? But any spanning tree must include all vertices. If we try to avoid using v1 as a hub, we might still need to connect v1. Perhaps a tree like: (v1,v2) cost 2, (v2,v3) cost 101, (v2,v4) cost 101. That total = 2+101+101=204. The tree using v1 as hub: (v1,v2) 2, (v1,v3)101, (v1,v4)101 total = 204 as well. So same. But is there a tree that uses (v1,v2) and (v2,v3) and (v3,v4)? That would be 2 + 101 + 200 = 303, worse. So both are same cost.

    But could there be a tree that uses (v2,v3) but not (v1,v3) and not (v1,v2)? But then v1 must be connected: maybe (v1,v3) or (v1,v4) etc. Let's explore if our candidate set is sufficient to achieve optimal cost. Suppose we have two minima v1 and v2. Our set includes edges from v1 to all others, but not from v2 to others (except v1). If the optimal MST uses edge (v2,v3) (cost 101) instead of (v1,v3) (cost also 101). Since costs are equal, it's okay but our candidate set doesn't have (v2,v3) standard. Could the MST be forced to use (v2,v3) because (v1,v3) is not available due to some constraints? But we have (v1,v3) in the set, cost 101. So we can use that. However, what if there is a special offer (v1,v3) that is expensive (say 200) but (v2,v3) standard 101? Wait, special offer for (v1,v3) could be worse than standard? Actually if there is a special offer for (v1,v3) with w > 101, we wouldn't use it because we also have the standard edge (v1,v3) at 101. So we have standard edge from v1 to v3. So it's available. So the only scenario where we might miss a cheaper connection is if the cheapest way to connect v3 to the rest is via v2 and the edge (v2,v3) has cost cheaper than (v1,v3). But as argued, since a1 = a2, costs are equal. If a1 < a2 (i.e., v1 is unique min), then (v1,v3) <= (v2,v3) because a1 <= a2. So (v1,v3) is cheaper or equal. So we are not missing any better edge. So the candidate set is safe.

    But consider if there is a special offer that makes (v2,v3) cheaper than (v1,v3) even though a2 > a1? For example, a1=1, a2=10, a3=100. Standard: (v1,v3)=101, (v2,v3)=110. So (v1,v3) is cheaper. However, if there is a special offer for (v2,v3) at cost 50, which is much cheaper than 101. That's a special offer, and we include it. So it's present. So fine.

    Thus candidate set includes all edges that could be beneficial: either special offers (any pair) or standard edges from global min to others. So seems complete.

    Now, more rigorous reasoning: For any edge (i,j) with cost c = min(a_i+a_j, w_ij). If c = a_i + a_j (i.e., no special offer or special offer is not better), and if i != min and j != min, then a_min + a_j <= a_i + a_j (since a_min <= a_i). So the edge (min,j) has cost at most a_min + a_j <= a_i + a_j. But could (min,j) have a cheaper special offer? Possibly, but in any case, there exists an edge connecting min and j with cost <= a_min + a_j <= a_i + a_j. So we have an edge (min,j) in our set (either standard or special) with cost <= a_i + a_j. Similarly, there is edge (min,i) with cost <= a_i + a_j. So the edge (i,j) is dominated by at least one of those. For MST, dominated edges can be omitted without affecting the MST weight, provided the dominating edges are present. However, we must ensure that the domination is in the sense of cut property: For any cut, the cheapest edge crossing the cut must be present among our edge set. For MST equivalence, it's enough that for every cut, the minimum weight edge crossing that cut in the original complete graph is also present (or has weight equal to an edge that is present). Since we include all special offers and all min-to-others edges, does that guarantee that for any cut (S, V\S), the minimum edge crossing the cut in the original graph is represented? Consider a cut where min is on one side. The cheapest crossing edge could be either a special offer between some u in S and v in V\S, or a standard edge. If it's a standard edge, the cheapest standard edge crossing the cut is min (on whichever side) to the other side? Actually need to prove: For any cut, the cheapest edge in the original graph is either a special offer or a standard edge involving the global minimum. Let's check: Suppose we have a cut (S, V\S). Let min be in S (or possibly in V\S). Without loss, assume min in S. Consider any edge crossing the cut: (u in S, v in V\S). Its cost is min(a_u+a_v, w_uv). The cheapest among standard edges crossing the cut could be the one with minimal a_u + a_v. Since min is in S, the smallest a_u among S is a_min (by definition). Among V\S, let v* be vertex with smallest a_v. Then the edge (min, v*) has standard cost a_min + a_{v*}. For any other crossing edge (u,v), a_u >= a_min and a_v >= a_{v*}, so a_u + a_v >= a_min + a_{v*}. So the minimum standard cost crossing the cut is exactly a_min + min_{v in V\S} a_v, achieved by (min, v*). If there is a special offer crossing the cut with weight less than that, then that's the global minimum. So the minimum crossing edge in the original graph is either a special offer (any) or the standard edge (min, v*). And both are present in our edge set: the special offer is included; the standard edge (min, v*) is included because we added edges from min to all vertices (including v*). Thus for every cut, the minimum weight edge crossing it is present in our graph. This is a sufficient condition for the MST of the reduced graph to be an MST of the original graph (by cut property: if for every cut, the minimum edge of the original graph belongs to the reduced graph, then the MST of the reduced graph is also an MST of the original). Actually, we need that the reduced graph contains a minimum-weight edge for each cut. Then by the greedy cut property, any MST of the reduced graph, when considering all edges of original, would also be an MST. More formally, if G' is a subgraph of G (or at least has the same vertex set and edges are subset of G? Our reduced graph edges are all present in the original? Check: The original complete graph has an edge for every pair with cost = min(a_i+a_j, w_ij). Our reduced graph includes: special offers with weight w_ij, which corresponds to the original edge (since cost is min(a_i+a_j, w_ij) which could be w_ij if w_ij <= a_i+a_j; but if w_ij > a_i+a_j, then the original edge cost would be a_i+a_j, not w_ij. However, we are adding the edge with weight w_ij even if w_ij > a_i+a_j? In the special offer, we have the option to pay w coins, but we can also pay a_i+a_j. So the actual cost for that pair is min(a_i+a_j, w). In our reduced graph, we are adding an edge with weight w (special offer) separately, and also the standard edge with weight a_i + a_j. But if w > a_i + a_j, the original edge cost is a_i + a_j. If we add both, then the edge with weight w is not actually present in the original graph because the original cost is the minimum, which is a_i + a_j. However, including an edge with higher weight than the true cost could affect MST if we mistakenly use it. But we must be careful: In the original graph, for a pair with a special offer, there is exactly one edge with cost = min(a_i + a_j, w). It is not two edges; it's one edge with that cost. So in our reduced graph, we should model exactly that: we should have exactly one edge per pair, with the correct cost. Including both a special offer edge with weight w and a standard edge with weight a_i + a_j for the same pair would potentially allow us to choose a cheaper edge than the true cost if w < a_i + a_j, but if w > a_i + a_j, then we would be allowing an edge with weight w that is not actually available (since we could always choose the standard cost instead). However, if w > a_i + a_j, the true cost is a_i + a_j. So we should not include the special offer as a separate edge with weight w because that would be an extra option that doesn't exist (since we could pay w, but we could also pay a_i+a_j which is cheaper; the cost is min(...). In the problem statement: "You may add an edge between 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." That means for a pair (x,y) that has a special offer, you have two options: pay w (using the offer) or pay a_x + a_y (standard). But you are not forced to use the offer; you can choose the cheaper. So effectively, the cost to add an edge between x and y is min(a_x + a_y, w). So indeed the true cost is min(...). So when constructing the graph, we should assign each pair a cost = min(a_i + a_j, w_ij). But we are trying to avoid building all pairs, so we approximate with edges: we include an edge for each special offer with weight w, and also for each vertex i (i != min) an edge (min,i) with weight a_min + a_i. However, if there is a special offer for (min,i) with w > a_min + a_i, then the true cost for that pair is a_min + a_i. But in our set, we have both: edge (min,i) with weight a_min + a_i (standard) and edge (min,i) with weight w (special). The true edge should have cost a_min + a_i (since min). If we include the special edge with weight w > a_min + a_i, then during MST we might accidentally pick the standard edge (since it's cheaper) and ignore the special one, which is fine because we are picking the cheaper, which matches true cost. But the problem is: the presence of the extra edge (with higher weight) does not harm because it won't be selected if cheaper alternative exists. However, could it cause an issue if we are forced to use it due to connectivity? No, because MST always picks cheapest edges first, and if the components become connected via cheaper edges, the higher weight edge will be skipped. So including a higher weight edge does not increase the MST cost; it's just redundant. But careful: What about a pair (i,j) that is not min and has a special offer with w > a_i + a_j? The true cost is a_i + a_j. In our reduced graph, we are not including any edge for (i,j) unless it's a special offer. We are including the special offer edge with weight w, but we are not including the standard edge (i,j) with weight a_i + a_j because we only include standard edges from min. So for such a pair, our graph would have an edge with weight w > a_i + a_j, whereas the true cost is a_i + a_j. This could lead to our MST being suboptimal because we might be forced to use a more expensive edge if the cheaper standard edge is not available. But we argued earlier that we don't need standard edges between non-min vertices because they are dominated by edges involving min. However, is that always true when the special offer is more expensive than the standard cost? For such a pair (i,j) with w > a_i + a_j, the true cost is a_i + a_j, which might be cheaper than using two edges via min. But we are not planning to use that edge at all; we are only considering using the edge (i,j) at cost a_i + a_j if it's beneficial. But our reduced graph does not contain this edge; it contains only the special offer edge with cost w (which is higher). So if the true cheapest way to connect i and j is via direct standard edge at cost a_i + a_j, but we omit it, could that cause our MST to have higher cost? Let's examine.

    Suppose we have vertices i and j, neither is min, and there is a special offer with w > a_i + a_j (so the true cost is a_i + a_j). In our reduced graph, we have only edges: special offer (i,j) with weight w (bad), and standard edges from min to i and min to j with weights a_min + a_i, a_min + a_j. Also possibly other special offers. The true MST of the original graph could include the edge (i,j) with cost a_i + a_j. But is it ever necessary to include such an edge? Could we replace it with something else without increasing cost? In the original graph, (i,j) is standard cost a_i + a_j. As argued earlier, we can replace it with edge (min, j) if min and i are in same component after removal, or with (min, i) otherwise. But note: The cost of (min,j) is a_min + a_j. Since a_min <= a_i, we have a_min + a_j <= a_i + a_j. So (min,j) is cheaper or equal. But is (min,j) always available? In the original graph, yes, there is an edge (min,j) with cost a_min + a_j (standard, or maybe lower via special). In our reduced graph, we have that edge (min,j) with cost a_min + a_j. So if we replace (i,j) with (min,j), we get a cheaper or equal connection. However, we must ensure that min and i are in the same component after removing (i,j). In the transformation we argued that after removing (i,j), min is in the same component as one of the endpoints. Suppose min is in same component as i. Then adding (min,j) connects the two components. The cost of (min,j) is a_min + a_j <= a_i + a_j. So we improve or equal. If min is in same component as j, then add (min,i). So indeed we can replace (i,j) with an edge involving min that is cheaper or equal. So the true MST would not need to use (i,j) because we can always replace it with a cheaper or equal edge from min to one of them, unless that replacement creates a cycle because min is already connected to both? Wait, but in the replacement process, we are constructing a new tree: we remove (i,j) and add (min,j). This yields a new spanning tree with cost <= original. So any MST that uses (i,j) can be transformed to one that does not use (i,j) and has no higher cost. Therefore, there exists an optimal MST that does not use any standard edge between two non-min vertices. So we can safely omit them. Even if the special offer for (i,j) is > a_i + a_j, we don't need to include the true edge because we can achieve the same or lower cost using min edges. Thus our reduced graph, which lacks the standard edge (i,j) but has the special offer edge (maybe higher), still contains an MST of the original graph (by using min edges instead). So it's fine.

    But what if the special offer is the only way to get an edge cheaper than min edges? Actually, if special offer w < a_min + a_i (for some i), it's included and will be used. If w > a_i + a_j and we don't include the standard edge, we might be missing a cheaper edge (a_i + a_j) but we have a cheaper alternative via min. So it's fine.

    Now, is it possible that for some pair (i,j) (non-min), a_i + a_j is actually less than both a_min + a_i and a_min + a_j? That would require a_min > a_i and a_min > a_j? But min is the minimum, so a_min <= a_i and a_min <= a_j. So a_min + a_i <= a_i + a_j (since a_min <= a_j). Similarly a_min + a_j <= a_i + a_j. So both are ≤. So indeed the min edges are cheaper or equal. So standard edge (i,j) is never cheaper than the min edges to each endpoint. So we can ignore them.

    Thus the reduction is valid.

    Now, what about the case where the min vertex is not unique and we pick one, but consider a pair of two other minima (both have value equal to min) but our hub is only one min. Could there be a standard edge between those two minima that is cheaper than the hub's edges to them? Since both have value min, edge between them costs 2min. The hub's edge to each also costs min+min=2min. So equal. So not missing.

    Thus algorithm stands.

    Now, edge cases with very large values, but we use long long.

    Now, let's implement.

    But wait: Could there be a scenario where the MST uses an edge from a non-min vertex to min but the min is not the global min? No, we defined global min.

    Now, implement DSU.

    Potential optimization: We may not need to add all standard edges from min to others if there is already a special offer connecting min to that vertex with a cost <= a_min + a_i. But adding both is fine.

    Now, we must be cautious about memory: edges vector of size m + n-1. Store as vector of arrays of 3 ints? Use tuple or struct.

    Now, code.

    We'll parse input with scanf or cin fast I/O.

    Now, let's test with some random cases to ensure logic.

    But before coding, think about possible pitfalls: The special offers might include self-loops? Input says x != y, so fine.

    Now, confirm the MST property: The cut argument ensures that the minimum edge across any cut is present. That is sufficient: If for every cut, the minimum-weight edge in the original graph is also present in the reduced graph, then the minimum spanning tree of the reduced graph (which is a subgraph) will be an MST of the original graph. Because consider any MST T of original. For each edge e in T, consider the cut defined by the two components when removing e. The weight of e is the minimum among edges crossing that cut (by cut property of MST). Since our reduced graph also contains that minimum edge (maybe not e but some other edge with same weight or less?), Actually we need that the reduced graph contains some minimum-weight edge for each cut, not necessarily the same one. However, if for each cut, the reduced graph contains at least one edge that is minimum weight for that cut, then the MST of the reduced graph (which might pick a different edge for that cut) will still have total weight equal to the MST weight of the original graph. More precisely, the set of minimum edges across cuts are enough to construct an MST. The reduced graph is a subgraph that contains all such edges. Then any MST of the reduced graph is an MST of the original because the original graph's edge weights are at least those in the reduced graph? Actually careful: The reduced graph might have some edges that are heavier than the original (like special offers that are more expensive than the true cost). But we argued that such edges are not needed; we only need to include the true min edges for each cut. But our reduced graph may contain extra heavier edges but also includes the true min edges for each cut? Let's verify: For a cut (S, V\S), we need that the reduced graph contains an edge that achieves the minimum crossing weight in the original graph. As argued, the minimum crossing weight is either a special offer with weight w < a_min + min_{other} a, or the standard edge (min, v*) with cost a_min + a_{v*}. Our reduced graph includes all special offers, so if the min crossing edge is a special offer, it's present. If it's the standard edge (min, v*), it's present as we add it. So indeed for every cut, the reduced graph contains at least one edge with weight equal to the minimum crossing weight. Actually, we need to ensure that the edge (min, v*) is indeed the minimum standard edge; and we include it (standard or possibly a cheaper special). So yes, the reduced graph contains an edge with weight exactly the minimum crossing cost. Thus the minimum crossing edge is present. Therefore, by the cut property, the MST of the reduced graph will have the same weight as the MST of the original, because any MST of the reduced graph can be grown using only edges that are minimum for some cut. I think it's a known lemma: If a graph G' contains for each cut at least one edge that is lightest in G for that cut, then the weight of the minimum spanning tree of G' equals the weight of the minimum spanning tree of G. And any MST of G' is an MST of G (since G' is a subgraph of G? Not necessarily a subgraph because edges in G' might have different weights than in G? Actually in G', edges have weights that are exactly the cost of that connection: for a special offer we set weight w, which is exactly the cost if we choose the offer, but the true cost of that pair is min(a_i+a_j, w). So the edge weight in G' might be larger than the true cost if w > a_i+a_j. But note: In our reduced graph, we also have the standard edge (min,i) with weight a_min + a_i, which matches true cost. So for a pair (i,j) with special offer w > a_i+a_j, the true cost is a_i+a_j. In G', we might have an edge (i,j) with weight w (higher) and also might have edges from min to i and j. The true minimum crossing edge for a cut might be a_i+a_j (if that is less than anything else). But we argued that a_i+a_j is not less than a_min + a_i or a_min + a_j. So the minimum crossing weight for any cut will never be a_i+a_j when i and j are non-min, because there is always a cheaper edge via min (if min is on one side of the cut). But what if the cut separates min from both i and j? Actually if min is in S, and both i and j are in V\S, then the crossing edges are from min to i, min to j, and also possibly i-j if both are on the other side? Actually i and j are both in V\S, so edge i-j does not cross the cut. So it's irrelevant. So the crossing edges are those from vertices in S to vertices in V\S. If min is in S, then the edges from min to each vertex in V\S are crossing. So the minimum among those is min over v in V\S of (cost(min,v)). That is at most a_min + a_v. So no need for i-j. If min is in V\S, symmetric. If neither side contains min? That's impossible because min is a vertex, so it's in exactly one side. So indeed, the minimum crossing edge is always either a special offer crossing the cut or a standard edge involving the global min. So we have it.

    Thus algorithm is correct.

    Now implement.

    We'll use 0-index for vertices.

    Pseudo:

    struct Edge { int u, v; long long w; bool operator<(const Edge& other) const { return w < other.w; } };

    Then:

    vector edges; edges.reserve(m + n - 1);

    Read special offers, for each: edges.push_back({x-1, y-1, w});

    After reading a[] and finding min_idx:

    for i in 0..n-1: if i != min_idx: edges.push_back({min_idx, i, a[min_idx] + a[i]});

    Now sort.

    DSU:

    class DSU { vector parent, rank/size; public: DSU(int n) { parent.resize(n); for i.. parent[i]=i; size.resize(n,1); } int find(int x) { return parent[x]==x? x : parent[x]=find(parent[x]); } bool unite(int x, int y) { x=find(x); y=find(y); if(x==y) return false; if(size[x] < size[y]) swap(x,y); parent[y]=x; size[x]+=size[y]; return true; } };

    Then:

    long long total=0; int taken=0; for(auto& e: edges) { if(dsu.unite(e.u, e.v)) { total += e.w; taken++; if(taken == n-1) break; } }

    cout << total;

    Now check with examples.

    Example1: n=3, a=[1,3,3], min_idx=0. edges: specials: (1,2,5) and (1,0,1) (since x,y given 2 3 5 and 2 1 1, after -1: (1,2,5) and (1,0,1). standard: (0,1,4), (0,2,4). Sort: w=1 (0,1), w=4 (0,1 duplicate? but (0,1) already used, but we have (0,1) with w=4 also, but after union, they are already connected, so ignored. Next w=4 (0,2) then w=5 (1,2). So picks 1 and 4 => total 5.

    Example2: n=4, a=[1,3,3,7], min_idx=0. edges: standard: (0,1)=4, (0,2)=4, (0,3)=8. m=0. sort: 4,4,8. total=16.

    Example3: n=5, a=[1,2,3,4,5], min_idx=0. special offers: (0,1,8), (0,2,10), (0,3,7), (0,4,15). standard: (0,1)=3, (0,2)=4, (0,3)=5, (0,4)=6. Sort: 3 (0,1), 4 (0,2), 5 (0,3), 6 (0,4), 7,8,10,15. MST picks first four: 3+4+5+6=18.

    All match.

    Now test with a custom scenario: n=4, a=[10,1,100,100], m=1 special: (2,3,150). min_idx=1 (a=1). standard edges: (1,0)=11, (1,2)=101, (1,3)=101. special: (2,3,150). Sort: 11,101,101,150. MST cost = 11+101+101=213. Is this optimal? Could we do better by using special (2,3) =150 instead of one of the 101 edges? But then we need to connect both 2 and 3: if we use (2,3)=150, then we need to connect the component {2,3} to {1,0}. The cheapest edge between them is (1,2)=101 or (1,3)=101. So total = 11+150+101=262, worse. So 213 optimal. Our algorithm yields 213.

    Now test with scenario where special offer is cheaper than min edge: n=3, a=[5,10,100], m=1 offer (1,2,20) (vertices 1-indexed: (2,3,20)? Actually to test: let min_idx=0 (a=5). standard edges: (0,1)=15, (0,2)=105. offer (1,2,20). Sort: 15,20,105. MST picks 15 and 20? After picking 15, components: {0,1} and {2}. Next cheapest crossing: 20 (1,2) connects => total 35. Is that optimal? Alternative: use 20 and 105? total 125, worse. So 35. But is there a possibility to use 15 and 105? That would be 120, worse. So good.

    Now test with scenario where offer is cheaper than standard from min to that vertex: n=3, a=[5,100,100], m=1 offer (0,1,10). min_idx=0. standard: (0,1)=105, (0,2)=105. offer: (0,1,10). So edges: (0,1,10), (0,1,105), (0,2,105). Sorted: 10,105,105. MST: pick 10, then need connect vertex2: cheapest is (0,2)=105 => total 115. Could we use (0,2)=105 and (1,2)=200? worse. So 115. Could there be a better tree using only standard edges? That would be 105+105=210. So 115 is better.

    Now test with n=2, a=[5,100], m=1 offer (1,2,150). min_idx=0. standard: (0,1)=105. offer: (0,1,150). Sorted: 105,150. MST picks 105. But note: the true cost for (1,2) is min(150,105)=105, so correct.

    Now test with n=4, a=[1,100,101,102], m=2 offers: (2,3,180) and (3,4,105). min_idx=0. standard: (0,1)=101? Actually a0=1, a1=100 => 101, (0,2)=102, (0,3)=103. offers: (1,2,180), (2,3,105). Sorted: 101,102,103,105,180. MST picks 101 (0-1), 102 (0-2), then need to connect vertex3: options: (0,3)=103, (2,3)=105. So picks 103 => total 306. Could there be a better using (2,3)=105 and not (0,2)? Suppose we pick 101 (0-1), then 105 (2-3) connects 2 and 3, but we still need to connect component {2,3} to {0,1}. Cheapest edge between: (0,2)=102 or (0,3)=103 or (1,2)=180 or (1,3)=? (1,3) standard cost 100+102=202? Actually a1=100, a3=102 =>202, but we haven't added that edge; we only have standard from min. So the cheapest is 102. Total = 101+105+102=308. So 306 is better. So our algorithm yields 306.

    Now, what about a case where special offer (2,3)=90 (cheaper than (0,2)=102 and (0,3)=103)? Then edges: 101,90,102,103. Sorted: 90,101,102,103. MST: pick 90 (2-3), then 101 (0-1), now we have components: {0,1} and {2,3}. Cheapest crossing: (0,2)=102 or (0,3)=103 or (1,2)=? (1,2) standard 100+101=201 not in set; but we have (1,2) maybe no offer; but we have only (0,2) and (0,3). So cheapest is 102. Total = 90+101+102=293. Could there be a better: maybe 101 and 102 and 103? That's 306. So 293 optimal. Our algorithm picks that.

    Thus works.

    Now consider if there is a special offer (1,2) that is cheaper than (0,1) and (0,2) but still not as cheap as using something else? Already covered.

    Now, we must also consider the possibility that we could use multiple special offers and maybe not use any standard edges from min. That's fine.

    Now, let's think about large constraints: Sorting 400k edges, each with weight up to 1e12, use long long. DSU operations O(alpha(n)). So overall fine.

    Now, is there any case where we need to consider edges from min to others with weight a_min + a_i, but what if there is a special offer for (min,i) that is cheaper, we include it; but the standard edge is still added; that's okay.

    Now, edge case: n=0? Not possible.

    Now, think about memory: edges vector of size up to 400k, each edge storing two ints and a long long, okay.

    Now, about reading input: use scanf for speed, or cin with ios_base sync.

    Now, DSU implementation.

    Now, potential overflow: sum of costs could be up to (n-1)*max_edge_weight ~ 2e5 * 2e12 = 4e17, still within signed 64-bit? 2^63-1 ≈ 9.22e18, so safe.

    Now, finalize.

    But wait: There is another nuance: The standard edges from min to i have cost a_min + a_i. However, suppose there is a special offer for (min,i) with weight w < a_min + a_i. Then the true cost for connecting min and i is w, not a_min + a_i. In our edge set, we have both: one with weight w (special) and one with weight a_min + a_i (standard). Sorting will pick w first. So the MST will use the special if beneficial. So fine.

    Now, the only thing: In the reduced graph, we might have two edges between the same pair (min,i) with different weights. That's okay.

    Now, one more potential improvement: Since we only need standard edges from min, we could avoid adding them if there is already a special offer with weight <= a_min + a_i? But not necessary.

    Now, code.

    But before finalizing, think about the following: Could there be a scenario where the MST of the reduced graph has weight higher than the true MST because we omitted a standard edge that is actually cheaper than any min edge? As argued, no. But let's test a contrived case with multiple minima: a = [1,1,100,200]. min_idx=0 (value 1). Standard edges: (0,1)=2, (0,2)=101, (0,3)=201. Suppose there is a special offer (1,2) with w=150 ( > a1+a2=101? Actually a1=1, a2=100 => 101, so w=150 >101, so true cost for (1,2) is 101, but we don't have that edge in our set. We have only (0,2) with 101 and (0,1) with 2. Could the true MST be: (0,1)=2, (1,2)=101, (2,3)=? to connect 3, we could use (2,3) standard 300 or (0,3)=201. So total = 2+101+201=304? Wait, (0,3)=201, total = 2+101+201=304. Alternatively, using our reduced graph edges: (0,1)=2, (0,2)=101, (0,3)=201 total = 304 as well. Same. Could there be a tree using (1,2)=101, (1,3)=? a1+a3=1+200=201, (0,1)=2 => total 2+101+201=304. Or (0,2)=101, (2,3)=300 => 2+101+300=403 worse. So all same.

    Now consider if there is a special offer (1,3)=150 (which is < a1+a3=201, but > a0+a3=1+200=201? Actually a0=1, a3=200 => 201; so 150 < 201. So true cost for (1,3) is 150. Our reduced graph includes that special offer. So we can use it. Without that, we'd have to use 201. So good.

    Thus no problem.

    Now, confirm with random tests.

    I'll write a small brute-force for n up to 8 to compare with full graph MST (using all pairs) and our reduced graph MST.

    But since we are reasoning, it's fine.

    Thus solution is final.

    Now, we must consider time limit. Sorting 400k edges is fine. But note: n up to 200k, m up to 200k, so edges = 200k + 199999 = 399999, ~4e5. Sorting 4e5 is okay.

    Now, implement.

    I will write code in C++.

    Plan:

    #include <bits/stdc++.h> using namespace std;

    typedef long long ll;

    struct Edge { int u, v; ll w; bool operator<(const Edge& other) const { return w < other.w; } };

    class DSU { public: vector parent, sz; DSU(int n) { parent.resize(n); sz.resize(n, 1); for (int i = 0; i < n; i++) parent[i] = i; } int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (sz[x] < sz[y]) swap(x, y); parent[y] = x; sz[x] += sz[y]; return true; } };

    int main() { ios::sync_with_stdio(false); cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    int min_idx = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] < a[min_idx]) min_idx = i;
    }
    
    vector<Edge> edges;
    edges.reserve(m + n - 1);
    for (int i = 0; i < m; i++) {
        int x, y; ll w;
        cin >> x >> y >> w;
        x--; y--;
        edges.push_back({x, y, w});
    }
    
    // Add standard edges from min vertex to all others
    for (int i = 0; i < n; i++) {
        if (i != min_idx) {
            edges.push_back({min_idx, i, a[min_idx] + a[i]});
        }
    }
    
    // Kruskal
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    ll total = 0;
    int taken = 0;
    for (Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            taken++;
            if (taken == n - 1) break;
        }
    }
    
    cout << total << '\n';
    
    return 0;
    

    }

    Check for n=1: edges will be empty because m may be 0 and no standard edges added (since i != min_idx fails). So taken remains 0, total 0, output 0. Good.

    Now, edge: if m has duplicates? fine.

    Now, we must be careful that the special offers may be up to 200k, and some may be for pairs that are also added as standard edges from min. That's fine.

    Now, confirm that the graph is connected with these edges: standard edges from min to all others ensure connectivity regardless of special offers. So MST always exists.

    Now, done.

    But before finalizing, let's reflect on a possible alternative: Could we also ignore special offers that are worse than a_i + a_j? But we need them because they could be beneficial if they involve non-min vertices where a_i + a_j might be high but special offer is low. So we keep all.

    Now, just in case there is a special offer (x,y) with w >= a_x + a_y, it's not useful because we can get cheaper via standard min edges? But maybe it's useful if both x and y are not min, but the min edge to each is a_min + a_i. The special offer might still be cheaper than a_min + a_i? For w >= a_x + a_y, since a_x + a_y >= a_min + a_x and a_min + a_y (since a_min <= both), w is at least a_x + a_y, which is >= a_min + a_x and a_min + a_y. So the special offer is not cheaper than the min edges. So it won't be used. But we can still include it; it will be ignored by MST.

    Now, verify memory and time.

    Now, submit.

    But wait: Is there a scenario where the MST of the reduced graph might not be connected because we didn't include enough edges? But we have edges from min to all others, so the graph is definitely connected. So MST exists.

    Now, one more nuance: In the transformation we assumed we can replace any standard edge (i,j) with (min,j) if min and i are in same component. But what if min is not in the same component as either i or j? That cannot happen because tree is connected; after removing edge (i,j), the tree splits into two components. Since min is somewhere, it must be in exactly one of these components. So yes.

    Thus algorithm is correct.

    Now, I'll produce final answer. ```cpp #include <bits/stdc++.h> using namespace std;

    typedef long long ll;

    struct Edge { int u, v; ll w; bool operator<(const Edge& other) const { return w < other.w; } };

    class DSU { vector parent, sz; public: DSU(int n) { parent.resize(n); sz.resize(n, 1); for (int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (sz[x] < sz[y]) swap(x, y); parent[y] = x; sz[x] += sz[y]; return true; } };

    int main() { ios::sync_with_stdio(false); cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    int min_idx = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] < a[min_idx]) min_idx = i;
    }
    
    vector<Edge> edges;
    edges.reserve(m + n - 1);
    for (int i = 0; i < m; ++i) {
        int x, y; ll w;
        cin >> x >> y >> w;
        --x; --y;
        edges.push_back({x, y, w});
    }
    
    // standard edges from the cheapest vertex to all others
    for (int i = 0; i < n; ++i) {
        if (i != min_idx) {
            edges.push_back({min_idx, i, a[min_idx] + a[i]});
        }
    }
    
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    ll total = 0;
    int taken = 0;
    for (Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            ++taken;
            if (taken == n - 1) break;
        }
    }
    
    cout << total << '\n';
    return 0;
    

    }