前置知识：并查集、排序

Kruskal 的思想就是，每次都取一张图中的最小长度的边，如果出现了环，那就代表这个边是多余的，就不选。如果总共选到的边的数量（amt）是等于顶点数（n）-1，那么就已经构成了连通图，退出即可。如果直到算法结束，边的数量还没达到顶点数-1，那就代表这张图是一张非连通图。

对于判定选出的边是否出现了环，可以使用并查集实现。在每次选择边的时候，将这两个边放入到同一个集合中，那么可以知道，在这个集合中的顶点都是互相连通的。如果下一次选到的边的两个顶点在同一个集合中，我们就不选，因为他们已经连通过了。

代码有点长，但是思路很简单：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

#define inf 0x3f3f3f3f
#define int long long
#define endl '\n'

const int maxn = 5010;
const int maxm = 200010;

int n, m;
int ans, amt;

struct Edge {
    int from, to, w;
} e[maxm];
int cnt;

void add(int u, int v, int w) {
    e[++cnt].from = u;
    e[cnt].to = v;
    e[cnt].w = w;
    return;
}

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int fa[maxn];

void init() {
    for (int i = 0;i < maxn;i++) {
        fa[i] = i;
    }
    return;
}

int get(int x) {
    if (fa[x] == x) {
        return fa[x];
    } else {
        return fa[x] = get(fa[x]);
    }
}

void merge(int x, int y) {
    x = get(x), y = get(y);
    if (x != y) {
        fa[x] = y;
    }
    return;
}

signed main() {
    IOS;
    init();

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

    sort(e + 1, e + cnt + 1, cmp);

    for (int i = 1;i <= cnt;i++) {
        if (get(e[i].from) != get(e[i].to)) {
            merge(e[i].from, e[i].to);
            ans += e[i].w;
            amt++;
        }
        if (amt == n - 1) {
            break;
        }
    }

    if (amt != n - 1) {
        cout << "Error!" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

//Fununugugu Code