MST with Meraj

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;

// ...Defines...
/*{{{*/

#define sep " "
#define F first
#define S second
#define pb push_back
#define bug cout<<"OK!"<<endl;
#define all(x) (x).begin(), (x).end()
#define PRINT(x); for(auto &i : x){cout << i << sep;} cout << endl;
#define INPUT(x); for(auto &i : x){cin >> i;}

typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;

/*}}}*/

// ...DATA...
const int N = 2e5 + 5, MOD = 998244353, lg = 20;
ll inf = 1e18;

int n,m;
struct Edge{
	int u, v, w;

	bool operator<(const Edge &r){
		return w < r.w;
	}
};


struct DSU{
	
	int par[N], sz[N];

	void build(){
		for(int i = 0; i < n; i++){
			par[i] = i; sz[i] = 1;
		}
	}

	int root(int v){
		return par[v] = (par[v] == v ? v : root(par[v])); 
	}

	bool merge(int v, int u){
		v = root(v); u = root(u);
		if(v == u){return 0;}

		if(sz[v] < sz[u]){swap(u, v);}
		par[u] = v; sz[v] += sz[u];
		return 1;
	}

}dsu;


signed main(){
	ios::sync_with_stdio(false); cin.tie(nullptr); 

	cin >> n >> m;
	vector<Edge>edge;
	for(int i =0, u, v, w; i < m; i++){
		cin >> u >> v >> w;
		edge.pb({--u,--v,w});
	}
	
	// ...MST...

	dsu.build();
	sort(all(edge)); 

	ll W = 0;
	for(auto &[u, v, w] : edge){
		if(dsu.merge(u, v)){
			W += w;
		}
	}
	
	cout << W << endl;
}