$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

算法流程：
1. 将所有边按照边权升序排序（$O(m~\log~m)$）
2. 枚举每条边 $(a,b)$，如果这两个点不连通则把这条边加入最小生成树。

#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 100010;
int p[M], n, m;
struct E{
    int a, b, w;
    bool operator< (const E &W) const {
        return w < W.w;
    }
}edge[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    else return x;
}
int K() {
    int res = 0, cnt = 0;
    for (int i= 0; i <= m; i++) {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        if (find(a) != find(b)) {
            p[find(a)] = p[find(b)];
            cnt++; res += w;
        }
    }
    if (cnt == n - 1) return res;
    else return 0x3f3f3f3f;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) p[i] = i;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin>>a>>b>>w;
        edge[i] = {a, b, w};
    }
    sort(edge, edge+m);
    int t = K();
    if (t == 0x3f3f3f3f) puts("impossible");
    else cout<<t;
    return 0;
}