#include<iostream>

using namespace std;

void citire();
void afisare();
void back(int k);

int y[100], p[100],n , s;
int a[100][100];

int main()
{
  citire();
  y[1] = 1;
  p[1] = 1;
  back(2);

  return 0;
}

void citire()
{
    int i,j;
    cin >> n;
    for(i=1; i<=n; i++)
      for(j=1; j<=n; j++)
         cin >> a[i][j];
}


void afisare()
{
    cout << endl;
    for(int i=1; i<=n; i++)
        cout << y[i] << " ";
    cout << endl << s;
}

void back(int k)
{   int min=100000, imin;
    for(int i=1; i<=n; i++)
        if(!p[i] && a[y[k-1]][i]< min && i!=y[k-1])
        {
            min = a[y[k-1]][i];
            imin = i;
        }
    y[k] = imin;
    p[imin] = 1;
    s = s+a[y[k-1]][imin];
    if(k==n)
        afisare();
    else
        back(k+1);
}