#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

typedef vector<vector<int>> graph;
const int INF = int(1e9);

void print(graph g)
{
    for (int i = 0; i < int(g.size()); ++i)
    {
        cout << i + 1 << ": ";
        for (int j = 0; j < int(g[i].size()) - 1; ++j)
            cout << g[i][j] + 1 << ", ";

        if (g[i].size() > 0)
            cout << g[i].back() + 1;
        else
            cout << "нет смежных вершин";

        cout << ";" << endl;
    }
}

void print2D(graph g)
{
    int n = int(g.size());
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n - 1; ++j)
            cout << setw(5) << g[i][j] << ",";
        cout << setw(5) << g[i][n - 1] << endl;
    }
}

// Написание данного алгоритма сильно упрощается, если использовать
// матрицу смежности, а не список смежности.
void init(graph *g, int n, int k)
{
    for (int i = 0; i < n; ++i)
    {
        auto v = new vector<int>(n, k);
        (*g)[i] = *v;
    }
}

graph prim(graph g, int n)
{
    graph mst(n);
    init(&mst, n, -1);

    vector<int> u(n, 0);
    u[0] = 1;
    while (true)
    {
        // Ищем ребро минимального веса с начальной вершиной среди уже
        // задействованных, а конечной - среди незадействованных
        int m = INF;
        int q = -1;
        int p = -1;

        // v - уже задействованная вершина
        for (int v = 0; v < n; ++v)
        {
            if (u[v] == 0) continue;

            // i - незадействованная вершина
            for (int i = 0; i < n; ++i)
            {
                if (i == v || u[i] == 1 || g[v][i] == -1) continue;

                if (g[v][i] < m)
                {
                    q = v;
                    p = i;
                    m = g[v][i];
                }
            }
        }

        if (q == -1) break;
        if (p == -1) break;

        mst[q][p] = m;
        mst[p][q] = m;
        u[p] = 1;
    }

    // Если количество рёбер (т.е. элементов матрицы, не равных -1) не равно
    // n - 1, то граф является несвязным и минимальное остовное дерево
    // не может быть построено.
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (mst[i][j] != -1) ++cnt;

    if (cnt / 2 != n - 1) mst.clear();

    return mst;
}

int main()
{
    cout << "Введите количество вершин: ";
    int n;
    cin >> n;

    cout << "Введите количество рёбер: ";
    int k;
    cin >> k;

    graph g(n);
    init(&g, n, -1);

    cout << "o----------------------o" << endl;
    cout << "| Нумерация вершин с 1 |" << endl;
    cout << "o----------------------o" << endl;

    cout << "Введите рёбра (неориентированные, взвешенные):" << endl;
    for (int i = 0; i < k; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        g[a][b] = c;
        g[b][a] = c;

        g[a][a] = 0;
        g[b][b] = 0;
    }

    cout << "Введённый граф:" << endl;
    print2D(g);

    graph mst = prim(g, n);
    if (mst.size() > 0)
    {
        cout << "Построено минимальное остовное дерево:" << endl;
        print2D(mst);
    }
    else
        cout << "Минимальное остовное дерево не может быть построено" << endl;

    return 0;
}