MST_Kruskal

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> MSTedges;
vector<vector<ll>> edges;
ll N,M;
class disjointSet
{
    public:
    ll *_rank, *parent,n;
    disjointSet(ll n)
    {
        _rank = new ll[n+1];
        parent =  new ll[n+1];
        this->n = n;
        MakeSet();
    }
    void MakeSet()
    {
        for(ll i = 1; i <= n; i++)
        {
            parent[i] = i;
            _rank[i] = 0;
        }
    }

    void Union(ll x, ll y)
    {
        ll xroot = Find(x);
        ll yroot = Find(y);

        if(_rank[xroot] > _rank[yroot])
        {
            parent[yroot] = xroot;
        }
        else
        {
            parent[xroot] = yroot;
            if(_rank[x] == _rank[y])
                _rank[x] = _rank[x]+1;
        }
    }

    ll Find(ll x)
    {
        if(x != parent[x])
        {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
};

bool compare(vector<ll> a, vector<ll> b)
{
   if(a[2] == b[2])
   {
       return a[0]+a[1]+a[2] < b[0]+b[1]+b[2];
   }
   return a[2] < b[2];
}

void MST_Kruskal(ll N)
{
    disjointSet obj(N);
    sort(edges.begin(),edges.end(),compare);
    for(ll i = 0; i < edges.size(); i++)
    {
        ll u = edges[i][0];
        ll v = edges[i][1];
        if(obj.Find(u) != obj.Find(v))
        {
            MSTedges.push_back(edges[i]);
            obj.Union(u,v);
        }
    }
}
int main()
{
    ll total_w = 0;
    cin >> N >> M;
    for(ll i = 0; i < M; i++)
    {
        ll u, v, w;
        vector<ll> a;
        cin >> u >> v >> w;
        a.push_back(u);
        a.push_back(v);
        a.push_back(w);
        edges.push_back(a);
    }
    MST_Kruskal(N);
    for(ll i = 0; i < MSTedges.size(); i++)
    {
        total_w += MSTedges[i][2];
    }
    cout << total_w << endl;
    return 0;
}