Evtyukhov_Tipovik4_ex7a

#include <bits/stdc++.h>
using namespace std;
int n;
const int INF = 1000000000;

int main(){

    n = 6;
    int m = 12;
    //cin >> n >> m;


    int gr[n][n];
    double g[n][n];

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            g[i][j] = INF;
            gr[i][j] = 0;
        }
    }
    for (int i = 0; i < n; i++)
        g[i][i] = 0;


    for (int i = 0; i < m; i++){
        int x, y, w;
        cin >> x >> y >> w;
        x--;
        y--;
        g[x][y] = w;
        g[y][x] = w;
    }


    vector<bool> used (n);
    vector<double> min_e (n, INF);
    vector<int> sel_e (n, -1);


    min_e[0] = 0;
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j=0; j<n; ++j)
            if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
                v = j;
        if (min_e[v] == INF) {
            cout << "No MST!";
            exit(0);
        }

        used[v] = true;
        if (sel_e[v] != -1){
            cout << v + 1<< "      " << sel_e[v] + 1 << endl;
            gr[v][sel_e[v]] = 1;
            gr[sel_e[v]][v] = 1;
        }
        for (int to=0; to<n; ++to)
            if (g[v][to] < min_e[to]) {
                min_e[to] = g[v][to];
                sel_e[to] = v;
            }
    }


    return 0;
}

/*
1 2 2
1 5 6
1 6 2
2 3 2
2 4 4
2 6 4
3 4 7
3 5 5
3 6 5
4 5 4
4 6 6
5 6 2
*/