Prim

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

const int MAX_WEIGHT = 1000000;

int n, m;
int **w;

void init() {
    cin >> n >> m;

    w = new int*[n];
    for (int i = 0; i < n; ++i) w[i] = new int[n];

    for (int i = 0; i < m; ++i) {
        int start, end, weight;
        cin >> start >> end >> weight;
        w[start][end] = w[end][start] = weight;
    }
}

int prim() {
    bool *check = new bool[n];
    vector<int> select;
    check[0] = true;

    int total = 0;

    select.push_back(0);

    while (select.size() < n) {
        int minWeight = MAX_WEIGHT;
        int next = -1;

        for (int i = 0; i < select.size(); ++i)
            for (int j = 0; j < n; ++j)
                if (w[select[i]][j] > 0 && !check[j])
                    if (w[select[i]][j] < minWeight) {
                        minWeight = w[select[i]][j];
                        next = j;
                    }

        if (next == -1) {
            cerr << "No minimum spanning tree";
            exit(1);
        }

        check[next] = true;
        total += minWeight;
        select.push_back(next);
    }

    return total;
}

int main()
{
    init();
    cout << "Minimum spanning tree weight: " << prim() << endl;

    return 0;
}