#include <iostream>
#include <vector>
#include <algorithm>
#define doShift(planetMap,lastVisitedPlanet) ((planetMap) - (1 << (lastVisitedPlanet)))
using namespace std;

int costOfFly[20][20];
int minCostOfWay[1000000][20];
int path[1000000][20];
int planetCount;

int TravellingMan(int planetMap, int lastVisitedPlanet)
{
    if (!doShift(planetMap,lastVisitedPlanet))
    {
        path[planetMap][lastVisitedPlanet] = -1;
        minCostOfWay[planetMap][lastVisitedPlanet] = 0;
        return 0;
    }
    if (path[planetMap][lastVisitedPlanet])
    {
        return minCostOfWay[planetMap][lastVisitedPlanet];
    }
    int inf =(1LL<<16) - 1LL;
    minCostOfWay[planetMap][lastVisitedPlanet] = inf;
    for (int planet = 0; planet < planetCount; planet++)
    {
        if (planet != lastVisitedPlanet && ((planetMap >> planet)&1))
        {
            int tmp = TravellingMan(doShift(planetMap,lastVisitedPlanet), planet) + costOfFly[planet][lastVisitedPlanet];
            if (minCostOfWay[planetMap][lastVisitedPlanet] > tmp)
            {
                minCostOfWay[planetMap][lastVisitedPlanet] = tmp;
                path[planetMap][lastVisitedPlanet] = planet + 1;
            }
        }
    }
    return minCostOfWay[planetMap][lastVisitedPlanet];
}

void printPath(int t, int resLastVisitedPlanet)
{
    if (resLastVisitedPlanet < 0)
    {
        return;
    }
    resLastVisitedPlanet--;
    printPath(doShift(t, resLastVisitedPlanet), path[t][resLastVisitedPlanet]);
    cout << resLastVisitedPlanet + 1 << " ";
}
main()
{
    ios_base::sync_with_stdio(0);
    freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
    cin >> planetCount;
    for(int i = 0; i < planetCount; i++)
    {
        for(int j = 0; j < planetCount; j++)
        {
            cin >> costOfFly[i][j];
        }
    }

    int resLastVisitedPlanet = 0;
    int visitedAllPlanets = (1 << planetCount) - 1;

    for (int tryEndPlanet = 0; tryEndPlanet < planetCount; tryEndPlanet++)
    {
        int tmp = TravellingMan(visitedAllPlanets, tryEndPlanet);
        if (tmp < minCostOfWay[visitedAllPlanets][resLastVisitedPlanet])
        {
            resLastVisitedPlanet = tryEndPlanet;
        }
    }
    cout << minCostOfWay[visitedAllPlanets][resLastVisitedPlanet] << endl;
    printPath(visitedAllPlanets, resLastVisitedPlanet+1);
    return 0;
}