#include <iostream>
#include <algorithm>

using namespace std;
// Класс Маршрут
class route {
    int *r, n;    // r – массив, представляющий маршрут; n – количество городов
    public:
    route(int num = 0) {
        n = num;
        r = new int[n];
        for (int i = 0; i < n; i++)
            r[i] = i;
    }
    route(const route&a) {
        n = a.n;
        r = new int[n];
        for (int i = 0; i < n; i++)
            r[i]=a.r[i];
    }    // конструктор копирования
    route & operator = (const route&a) {
        if (this != &a) {
            n = a.n;
            delete []r;
            r = new int[n];
            for (int i = 0; i < n; i++)
                r[i]=a.r[i];
        }
        return *this;
    }   // операция присваивания
    ~route() { if(r) delete []r; r = NULL; } // деструктор
    int route_price(int **);  // вычисляет стоимость маршрута по матрице стоимости
    bool next_route();   // вычисляет следующий маршрут, используя алгоритм Дейкстры
    friend ostream & operator << (ostream&, const route&); // вывод маршрута
};

int route::route_price(int **arr) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum +=arr[r[i]][r[i+1]];
    return sum;
}
bool route::next_route() {
    int i = 0;
    int j;
    for (int k = n-2; k >= 1; k--)
        if(r[k]<r[k+1]) {
        i = k;
        break;
        }
    if (!(i)) return false;
    for (int k = n-1; k >= i+1; k--)
        if(r[i]<r[k]) {
            j = k;
            break;
        }
        swap(r[i],r[j]);
    for (int low = i+1, high = n-1;low<high; low++,high--)
            swap(r[low],r[high]);
    return true;
}
ostream & operator << (ostream& out, const route& a) {
    for (int i = 0; i < a.n; i++) {
        out<<a.r[i]<<"\t";
    }
    return out;
}

int main() {
    int n;
    cin>>n;
    route d(n);
    int **cost = new int*[n];
    for (int i = 0; i < n; i++) {
        cost[i] = new int[n];
        for (int j = 0; j < n; j++) {
            cin>>cost[i][j];
        }
    }
    route temp = d;
    int min = d.route_price(cost);
     cout<<temp<<"\t"<<temp.route_price(cost)<<endl;
    while(temp.next_route()) {
         cout<<temp<<"\t"<<temp.route_price(cost)<<endl;
        int tmin = temp.route_price(cost);
        if (tmin<min) {
            d = temp;
            min = tmin;
        }
    }
    cout<<min<<endl<<d;
    for (int i = 0; i < n; i++) {
        delete [] cost[i];
    }
    delete [] cost;
    return 0;
}
/*
5
0 3 1 3 4
5 0 3 2 4
4 4 0 2 4
4 8 2 0 4
2 8 7 1 0

13
0   1   3   2   4
*/