# Untitled

unknown
plain_text
2 months ago
1.5 kB
1
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"

const double PI = 3.14159265358979;
const ll INF =  1e9 + 7;
const ll MOD = 1e9 + 7;
const ll nax = 2505;
const int LOG = 25;

vector<int> par, sz;

int getParent(int x) {
return x == par[x] ? x : par[x] = getParent(par[x]);
}

void mergeGroups(int x, int y) {
x = getParent(x);
y = getParent(y);

if (x == y) {
return;
}

if (sz[x] < sz[y]) {
par[x] = y;
sz[y] += sz[x];
} else {
par[y] = x;
sz[x] += sz[y];
}
}

void solve() {
int n, m;
cin >> n >> m;

par.assign(n + 1, 0);
sz.assign(n + 1, 1);

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

vector<pair<int, pair<int, int> > > edges;

for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;

edges.push_back({w, {u, v}});
}

sort(edges.begin(), edges.end());
ll ans = 0, totalEdges = 0;

for (auto &edge: edges) {
int w = edge.first;
int u = edge.second.first;
int v = edge.second.second;

if (getParent(u) != getParent(v)) {
mergeGroups(u, v);
totalEdges++;
ans += w;
}
}

if (totalEdges == n - 1) {
cout << ans;
} else {
cout<< "IMPOSSIBLE";
}
}

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

// int t; cin >> t; while(t--)
solve();
return 0;
}```