#include <iostream>
#include <vector>
#include <limits>

    const int matrixSize = 8;
    const std::string titles[matrixSize] =
    {
        "Lantasovo", "Egorshino", "Orehovo", "Perm",
        "Voynovka", "Inskaya", "Omsk", "Ekaterinburg"
    };

class Cluster
{
    friend std::ostream& operator << (std::ostream&, Cluster&);
    friend Cluster* exists(std::vector<Cluster*>&, int);
    void print(std::ostream& os)
    {
        os << get_vertexes() << " SREZ = " << sr << std::endl;
    }

    std::vector<int> vx;
    std::vector<Cluster *> parents;
    int sr;

public:
    Cluster(int a, int b, int srez)
    {
        vx.push_back(a);
        vx.push_back(b);
        sr = srez;
    }
    Cluster(Cluster *first, int b, int srez)
    {
        vx.push_back(b);
        parents.push_back(first);
        sr = srez;
    }
    Cluster(Cluster *first, Cluster *second, int srez)
    {
        parents.push_back(first);
        parents.push_back(second);
        sr = srez;
    }

    std::string get_vertexes();
};
std::ostream& operator << (std::ostream& os, Cluster& cluster)
{
    cluster.print(os);
    return os;
}

std::string Cluster::get_vertexes()
{
    std::string res = "";
    for(unsigned i = 0; i < parents.size(); i++)
    {
        res += parents[i]->get_vertexes() + " ";
    }
    for(unsigned i = 0; i < vx.size(); i++)
    {
        res += titles[vx[i]] + " ";
    }
    return res;
}

Cluster* exists(std::vector<Cluster*> &cluster, int value)
{
    for(unsigned i = 0; i < cluster.size(); i++)
    {
        std::vector<int>::const_iterator it =
            std::find(cluster[i]->vx.begin(), cluster[i]->vx.end(), value);
        if(it != cluster[i]->vx.end()) return cluster[i];
    }
    return 0;
}

int main()
{
    int dm[matrixSize][matrixSize] =
    {
        {    0,  177,  171, 642,  981,   15, 403, 1315 },
        {  177,    0,  348, 465,  804,  192, 226, 1138 },
        {  171,  348,    0, 813, 1152,  156, 574, 1486 },
        {  642,  465,  813,   0,  339,  657, 239,  673 },
        {  981,  804, 1152, 339,    0,  996, 578,  334 },
        {   15,  192,  156, 657,  996,    0, 418, 1330 },
        {  403,  226,  574, 239,  578,  418,   0,  912 },
        { 1315, 1138, 1486, 673,  334, 1330, 912,    0 }
    }; // матрица смежности графа

    int sm[matrixSize][matrixSize];//матрица МОД
    int used[matrixSize];//использованные вершины
    int count=0;
    int min;

    for (int i=0; i< matrixSize; ++i)
    {
        used[i]=0;
        for(int j=0;j< matrixSize;++j) sm[i][j]=0;
    }

    used[0]=1;
    int idx;
    do
    {
        min=std::numeric_limits<int>::max();
        for(int i=0;i<matrixSize;++i)
        {
            if (used[i]!=0)
            {
                for(int j=0;j<matrixSize;++j)
                    if ( (dm[j][i] < min) && (dm[j][i]!=0) && (used[j]==0))
                    {
                        min=dm[j][i]; idx = j;
                    }
            }
        }

        for(int i=0;i < matrixSize;++i)
            for(int j=0;j<matrixSize;++j)
                if( (dm[j][i]== min) && (used[j]==0) &&(used[i]==1))
                {
                    used[j] =1;
                    sm[j][i]= sm[i][j] = min;
                    count++;
                    i=matrixSize;
                    break;
                }
    }
    while(count < matrixSize-1);

    // Выводим матрицу МОД ...
    for(int i = 0; i < matrixSize; i++)
    {
        for(int j = 0; j < matrixSize; j++)
        {
            std::cout << sm[i][j] << " ";
        }
        std::cout << std::endl;
    }

    std::vector<Cluster*> clusters;
    int ii, jj;
    for(int cycle = 1; cycle < matrixSize; cycle++)
    {
        min = std::numeric_limits<int>::max();
        for(int i = 0; i < matrixSize; i++)
        {
            for(int j = i + 1; j < matrixSize; j++)
            {
                if(sm[i][j] > 0 && sm[i][j] < min)
                {
                    min = sm[i][j]; ii = i; jj = j;
                }
            }
        }

        Cluster *iiC = exists(clusters, ii), *jjC = exists(clusters, jj);
        if(iiC && !jjC)
        {
            clusters.push_back(new Cluster(iiC, jj, min));
        }
        else
            if(jjC && !iiC)
            {
                clusters.push_back(new Cluster(jjC, ii, min));
            }
            else
                if(!iiC && !jjC)
                {
                    clusters.push_back(new Cluster(ii, jj, min));
                }
                else // exists(ii) && exists(jj)
                {
                    clusters.push_back(new Cluster(iiC, jjC, min));
                }
        sm[ii][jj] = 10000;
    }

    std::cout << clusters.size() << std::endl;
    std::vector<Cluster*>::iterator it;
    for(it = clusters.begin(); it != clusters.end(); it++)
    {
        std::cout << **it << std::endl;
    }

    return 0;
}