#include <iostream>
#include <vector>

using namespace std;


const int MAXN = 18; // максимальная размерность нашей задачи
const int INF = 1000000000; // импровизированная бесконечность

// колличество вершин
int n;
// матрица смежности исходного графа
int graph[MAXN][MAXN];

/*
 * в dp[mask][v] -- длинна кратчайшего
 * гамельтонова пути, который содержит все вершины mask,
 * и заканчивается в вершине v
 *
 * mask -- целове число
 * если j-ый бит числа mask равен единице,
 * то подразумевается, что гамильтонов путь содержит
 * вершину j
 */
int dp[(1 << MAXN)][MAXN];

// наш ответ -- искомый путь
int ans[MAXN];

// наш текущая лучшая длинна пути, и вершина, в которой этот путь заканчивается
// в конце программы тут будет лежать итоговая стоимость пути и вершина, в которой этот путь заканчивается
int cost = INF, bestv;

int main() {
    freopen("trader.in", "r", stdin);
    freopen("trader.out", "w", stdout);

/*
 * Эта задача о поиске кратчайшего пути в графе,
 * который содержит все вершины
 * Такой путь называется гамельтоновым
 *
 * Это задача коммивояжера о нахождении
 * кратчайшего гамельтоного цикла в ориентированном графе,
 * модифицированная для поиска гамельтонова пути
 */

    // считываем входные данные
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }

    // заполняем массив dp бесконечностями
    for (int mask = 1; mask < (1<<n); mask++) {
        for (int i = 0; i < n; i++) {
            dp[mask][i] = INF;
        }
    }

    /*
     * создаем базу нашей динамики
     * длинна пути, который содержит только первую вершину,
     * и заканчивается в ней же, равна нулю
    */
    dp[1][0] = 0;

    /*
     * 1 << a -- побитовый сдвиг на a позиций влево
     * равносилен умножению на 2^a
    */

    //перебираем все возможные множества вершин
    for (int mask = 0; mask < (1<<n); mask++) {
        // перебираем конец пути
        for (int i = 0; i < n; i++) {
            // перебираем вершину, из которой мы могли придти в вершину i
            for (int j = 0; j < n; j++) {
                // если вершины i и j есть в множестве mask и есть ребро между ними
                if (mask & (1<<j) && mask & (1<<i) && graph[j][i] > 0) {
                    // обновняем ответ для dp[mask][i]
                    dp[mask][i] = min(dp[mask][i], dp[mask - (1<<i)][j] + graph[j][i]);
                }
            }
        }
    }

    // ищем ответ -- путь завершился в одной из вершин 0 .. N - 1, и учавствуют все вершины
    for (int i = 0; i < n; i++) {
        if (cost > dp[(1<<n) - 1][i]) {
            cost  = dp[(1<<n) - 1][i];
            bestv = i;
        }
    }

    if (cost != INF) {
        // если ответ есть
        // восстанавливаем сам цикл

        // наша текущая вершина -- изначально мы в последней вершине
        int curv = bestv;
        // изначально рассматриваем множество всех вершин
        int mask = (1<<n) - 1;

        // добавляем текущую вершину в ответ
        ans[n - 1] = curv;
        /* cnt -- колличество вершин в пути в данный момент + 1
         * cnt -- итератор на текущее пустое место в массиве ответа
         * для записи следующей вершины
        */
        int cnt = 2;

        // пока в множестве есть вершины
        while (mask != 1) {
            // перебираем вторую вершину
            for (int i = 0; i < n; i++) {
                // если обе вершины в множестве и существует ребро и ..
                if ((mask & (1<<i)) != 0 && curv != i && graph[i][curv] > 0 &&
                    dp[mask][curv] == dp[mask - (1<<curv)][i] + graph[i][curv]) {
                    // делаем "шаг назад" -- обновляем mask и curv
                    mask -= (1<<curv);
                    curv = i;
                    // добавляем в ответ вершину curv
                    ans[n - cnt] = curv;
                    cnt++;
                }
            }
        }

        // выводим путь
        cout << cost << "\n";
        for (int i = 0; i < n; i++) {
            cout << ans[i] + 1 << " ";
        }
    } else {
        // иначе -- если не существует гамельтонова пути
        cout << -1;
    }
    return 0;
}