road_prep.cpp

#include <bits/stdc++.h>
//Author : ritchie_s
#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
// Short hand for usual tokens
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sp " "
// Shorthand for commonly used types
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
// functions
#define MOD 1000000007
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return (a/gcd(a,b))*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
// int gcd = __gcd(a,b) , ll LCM = 1LL*a*b/gcd
//solver fn

class dsu{
    public:
        int find(int i , vector<ll> &parent){
            if(i == parent[i]){
                return i;
            }
            return parent[i] = find(parent[i] , parent);  //size compression
        }
    
        //union fn along with rank compression
        void Union(int x , int y , vector<ll> &parent , vector<ll>&rank){
            int x_parent = find(x , parent);
            int y_parent = find(y , parent);
    
            if(x_parent == y_parent){
                return;
            }
    
            if(rank[x_parent] > rank[y_parent]){
                parent[y_parent] = x_parent;
            }
    
            else if(rank[x_parent] < rank[y_parent]){
                parent[x_parent] = y_parent;
            }
    
            else{
                parent[x_parent] = y_parent;
                rank[y_parent] += 1;
            }
        }
};
// parent vector--> parent[i] = i , rank vector initialized by 0
    
void solve(){
    ll n,m;
    cin>>n>>m;
    vvll edges;
    for0(i,m){
        ll u , v , wt;
        cin>>u>>v>>wt;
        edges.pb({wt , u , v});
    }

    sort(all(edges));

    dsu D ;
    vll parent(n+1) , rank(n+1);
    for1(i,n){
        parent[i] = i;
    }

    ll count = 0 , cost = 0;
    for(int i = 0 ; i<edges.size() ; i++){
        ll u = edges[i][1] , v = edges[i][2] , wt = edges[i][0];
        if(D.find(u,parent) != D.find(v,parent)){
            D.Union(u , v , parent , rank);
            cost += wt;
            count++;
            if(count == n-1) break;
        }
    }
    if(count != n-1) {
        cout<<"IMPOSSIBLE"<<endl;
        return;
    }
    cout<<cost<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
     int t=1;
     
     while(t--){
        solve();
     }
    return 0;
}