Shared code

// https://cses.fi/problemset/task/1675, Borůvka
#include "bits/stdc++.h"
using namespace std;
using LL = long long;
 
struct Dsu {
	int n;
	vector<int> p;
	Dsu(int n) : n(n), p(n) {
		iota(begin(p), end(p), 0);
	}
	int find(int v) {
		return p[v] == v ? v : p[v] = find(p[v]);
	}
	bool merge(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b)
			return false;
		p[b] = a;
		return true;
	}
};
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	int m; cin >> m;
	vector<array<int, 3>> e(m);
	for (auto& [a, b, w] : e) {
		cin >> a >> b >> w;
		--a, --b;
	}
 
	int cc = n;
	LL ans = 0;
	Dsu dsu(n);
	while (cc != 1) {
		vector<int> cheapest(n, -1);
		for (int i = 0; i < m; ++i) {
			auto [a, b, w] = e[i];
			int ra = dsu.find(a);
			int rb = dsu.find(b);
			if (ra != rb) {
				if (cheapest[ra] == -1 || w < e[cheapest[ra]][2])
					cheapest[ra] = i;
				if (cheapest[rb] == -1 || w < e[cheapest[rb]][2])
					cheapest[rb] = i;
			}
		}
		vector<int> to_merge;
		for (int i = 0; i < n; ++i) {
			if (dsu.find(i) == i) {
				if (cheapest[i] == -1) {
					cout << "IMPOSSIBLE\n";
					return 0;
				}
				to_merge.push_back(cheapest[i]);
			}
		}
		for (int i : to_merge) {
			auto [a, b, w] = e[i];
			if (dsu.merge(a, b)) {
				ans += w;
				--cc;
			}
		}
	}
	cout << ans << "\n";
}