1095F - Make It Connected

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxN = (int)2e5;
int parent[maxN];
long long a[maxN];

void make_set(int v) {
    parent[v] = v;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v]=find_set(parent[v]);
}

void union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if(u==v) return;
    if (a[u] < a[v]){
        parent[v] = u;
        a[v] = a[u];
    } else {
        parent[u] = v;
        a[u] = a[v];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    int m;
    cin>>n>>m;
    for (int i=0; i<n; i++){
        cin>>a[i];
    }

    vector<pair<long long,pair<int,int>>> possibleEdges;
    for (int i=0; i<m; i++){
        int x;
        int y;
        long long w;
        cin>>x>>y>>w;
        possibleEdges.push_back({w,{x-1,y-1}});
    }

    long long rootWeight = a[0];
    int root = 0;
    for (int i=1; i<n; i++){
        if (rootWeight > a[i]){
            root = i;
            rootWeight = a[i];
        }
    }

    for (int i=0; i<n; i++){
        if (i != root){
            possibleEdges.push_back({rootWeight+a[i],{root, i}});
        }
    }

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

    long long coins = 0LL;
    for (int i=0; i<n; i++){
        make_set(i);
    }
    for (int i=0; i<possibleEdges.size(); i++){
        int uSet = find_set(possibleEdges[i].second.first);
        int vSet = find_set(possibleEdges[i].second.second);
        if (uSet != vSet){
            coins+=possibleEdges[i].first;
            union_set(uSet,vSet);
        }
    }
    cout<<coins<<endl;
    return 0;
}