#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

//Функция конвертации матрицы смежности в список инцидентности
vector < pair < int, pair<int,int> > > ArrayConvToList(int **arr, int n)
{
    vector < pair < int, pair<int,int> > > res;// результирующий вектор

    for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
            if(arr[i][j]!=0)// если ребро существует
                res.push_back(make_pair < int, pair<int,int> >(arr[i][j],make_pair<int,int>(i,j)));

    return res;//вернем список
}

int **ptr;// костыль

// это наш функтор сортировки
struct sort_class
{
    bool operator()( pair<int,int> a, pair<int,int> b)
    {
        if (ptr[a.first][a.second]>ptr[b.first][b.second]) return 1;

        if (
            ptr[a.first][a.second]==ptr[b.first][b.second]
            &&
            a.second<b.second
            ) return 1;

        if (
            ptr[a.first][a.second]==ptr[b.first][b.second]
            &&
            a.second==b.second
            &&
            a.first<b.first
            ) return 1;
        return 0;
    }
} sort_object;

// главна функция
int main()
{
    //открываем файл для чтения
    ifstream in ("in.txt");//матрица смежности

    int n;// размерность
    in>>n;// читаем размер

    //выделяем память
    int **g = new int *[n];//под строку
    for (int i =0; i<n; i++)g[i] = new int [n];//под столбцы

    //читаем матрицу смежности
    for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++)
            in>>g[i][j];

    //преобразуем матрицу смежности в список инцидентности G = (V,E)
    vector < pair < int, pair<int,int> > > gl =  ArrayConvToList(g,n); // вес - вершина 1 - вершина 2

    //сортируем вектор
    sort (gl.begin(), gl.end());

    // инвертируем , т.к. нам надо найти максимальный остов
    reverse(gl.begin(), gl.end());

    //Принадлежность вершины тому или иному поддереву хранится в массиве
    //belonging - в нём для каждой вершины хранится номер дерева, которому она принадлежит.
    vector<int> belonging (n);

    //инициализация массива разными значениями
    for (int i=0; i<n; ++i) belonging[i] = i;

    vector < pair<int,int> > tree ;// максимальный остов

    int tw = 0;//total weight - общий вес

    for (int i=0; i<gl.size(); ++i)// идем по списку ребер
        if (belonging[gl[i].second.first] != belonging[gl[i].second.second])//если концы не пренадлежат разным деревьям
        {
            tw += gl[i].first;//увеличиваем общий вес дерева
            tree.push_back (make_pair (gl[i].second.first, gl[i].second.second));//добавляем ребро в результат

            int left = belonging[gl[i].second.second],
                right = belonging[gl[i].second.first];

            // объедением два дерева
            for (int j=0; j<n; ++j)
                if (belonging[j] == left)
                    belonging[j] = right;
        }


    //выводим результат
    ptr=g;
    sort(tree.begin(),tree.end(),sort_object);
    for (int i=0; i<tree.size(); ++i) if(tree.at(i).first<tree.at(i).second)swap(tree.at(i).first,tree.at(i).second);
    cout<<"Max tree:"<<endl;
    for (int i=0; i<tree.size(); ++i)
        cout<<tree.at(i).second+1<<" - "<<tree.at(i).first+1<<"\tW("<<g[tree.at(i).first][tree.at(i).second]<<")."<<endl;
    cout<<"total weight:\t"<<tw<<endl;

    return 0;
}