Prima

//Минимальное остовное дерево. Алгоритм Прима.
#include <iostream>
using namespace std;

const int N = 5555;
const int M = 111111;
const int INF = 1000000000;
int mn[N], es[M], ev[M], first[N], next[M], c, n, m;
bool b[N];

void add(int x, int y, int z) {
    next[++c] = first[x]; first[x] = c;
    es[c] = y; ev[c] = z;
}

int prim() {
    int ans = 0;// Вес минимального остова.
    for (int i = 2; i <= n; ++i) mn[i] = INF;
    for (int i = 1; i <= n; ++i) {
        int v = -1;
        for (int j = 1; j <= n; ++j)
            if (!b[j] && (v == -1 || mn[j] < mn[v])) v = j;
        b[v] = 1;
        ans += mn[v];
        for (int h = first[v]; h; h = next[h]) mn[es[h]] = min(ev[h], mn[es[h]]);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    cout << prim();
    return 0;
}