#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 35;
int n;
int c[N][N];
bool visited[N];
int choose[N];
int minc = INF;
int curc = 0;
int min_edge[N];
int total_min_edge = 0;
vector<vector<int>> all_answers;
void dq(int id) {
    int lb = curc + total_min_edge;
    if (lb > minc)
        return;
    for (int j = 2; j <= n; j++) {
        if (!visited[j]) {
            if (curc + c[choose[id - 1]][j] + (total_min_edge - min_edge[choose[id - 1]]) <= minc) {
                choose[id] = j;
                visited[j] = true;
                curc += c[choose[id - 1]][j];
                total_min_edge -= min_edge[choose[id - 1]];
                if (id == n) {
                    int final_cost = curc + c[choose[n]][1];
                    if (final_cost < minc) {
                        minc = final_cost;
                        all_answers.clear();
                        vector<int> path(choose + 1, choose + n + 1);
                        all_answers.push_back(path);
                    }
                    else if (final_cost == minc) {
                        vector<int> path(choose + 1, choose + n + 1);
                        all_answers.push_back(path);
                    }
                }
                else {
                    dq(id + 1);
                }

                total_min_edge += min_edge[choose[id - 1]];
                curc -= c[choose[id - 1]][j];
                visited[j] = false;
            }
        }
    }
}
int main() {
    cin >> n ;
    for (int i = 1; i <= n; i++) {
        min_edge[i] = INF;
        for (int j = 1; j <= n; j++) {
            cin >> c[i][j];
            if (j != i && c[i][j] < min_edge[i])
                min_edge[i] = c[i][j];
        }
        total_min_edge += min_edge[i];
    }
    choose[1] = 1;
    visited[1] = true;
    dq(2);
    if (all_answers.size() == 1) {
        cout << minc << endl ;
        for (int i = 0; i < n; i++) {
            cout << all_answers[0][i] << " " ;
        }
        cout << endl ;
    }
    else if (all_answers.size() > 1) {
        cout << minc << " " << all_answers.size() << endl ;
        for (const auto& path : all_answers) {
            for (int i = 0; i < n; i++) {
                cout << path[i] << " " ;
            }
            cout << endl ;
        }
    }
}