Kruskal

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n , m;
int num , ans;
int fa[5003];
struct node
{
    int u , v , w;
    bool operator < (const node &o) const
    {
        return w < o.w;
    }
}G[400003];
void init()
{
    for(int i = 1; i <= n; i++)
        fa[i] = i;
}
int getf(int x)
{
    if(x == fa[x])
        return x;
    return fa[x] = getf(fa[x]);
}
void Kruskal()
{
    sort(G + 1 , G + m + 1);
    for(int i = 1; i <= m; i++)
    {
        int t1 = getf(G[i].u) , t2 = getf(G[i].v);
        if(t1 == t2)
            continue;
        ans += G[i].w;
        fa[t1] = t2;
        num++;
        if(num == n - 1)
            break;
    }
}
int main()
{
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d" , &G[i].u , &G[i].v , &G[i].w);
    init();
    Kruskal();
    printf("%d" , ans);
    return 0;
}