//Stephen Siena
//CSE 40872 - Problem 15
//October 16, 2009

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

class Cell{
 public:
  Cell(){value = 0;}
  Cell(int v){ value = v;}
  
  int value;
  vector<int> path;
};

void findPath(vector<vector<Cell> >&, int);

int main(){

  int size;
  while(1){
    cin >> size;
    if (size == 0) break;

    vector<vector<Cell> > grid;

    grid.resize(size);
    for (int i = 0; i < size; i++){
      grid[i].resize(size);
    }
    
    for (int i = 0; i < size; i++){
      for (int j = 0; j < size; j++){
	cin >> grid[i][j].value;
      }
    }

    findPath(grid, size);
  }
  return 0;
}

void findPath(vector<vector<Cell> >& grid, int n){

  grid[0][0].path.push_back(grid[0][0].value);

  vector<int>::iterator it;

  for (int i = 1; i < n; i++){
    int left, up, diag;
    int r, c;
    for(r = 0, c = i; r <= i; r++, c--){
      if (r != 0)
	up = grid[r-1][c].value;
      if (c != 0)
	left = grid[r][c-1].value;
      if (r != 0 && c != 0)
	diag = grid[r-1][c-1].value;

      if (diag < up && diag < left && r != 0 && c != 0){
	for (it = grid[r-1][c-1].path.begin(); it != grid[r-1][c-1].path.end(); it++){
	  grid[r][c].path.push_back(*it);
	}
	grid[r][c].path.push_back(grid[r][c].value);
	grid[r][c].value += diag;
      }
      else if ((up < left && r != 0) || c == 0){
	for (it = grid[r-1][c].path.begin(); it != grid[r-1][c].path.end(); it++){
	  grid[r][c].path.push_back(*it);
	}
	grid[r][c].path.push_back(grid[r][c].value);
	grid[r][c].value += up;
      }
      else{
	for (it = grid[r][c-1].path.begin(); it != grid[r][c-1].path.end(); it++){
	  grid[r][c].path.push_back(*it);
	}
	grid[r][c].path.push_back(grid[r][c].value);
	grid[r][c].value += left;
      }	
    }
  }


  for (int i = n; i < 2*n-1; i++){
    int left, up, diag;
    int r, c;
    for(r = i-n+1, c = n-1; r < n; r++, c--){
      if (r != 0)
	up = grid[r-1][c].value;
      if (c != 0)
	left = grid[r][c-1].value;
      if (r != 0 && c != 0)
	diag = grid[r-1][c-1].value;

      if (diag < up && diag < left && r != 0 && c != 0){
	for (it = grid[r-1][c-1].path.begin(); it != grid[r-1][c-1].path.end(); it++){
	  grid[r][c].path.push_back(*it);
	}
	grid[r][c].path.push_back(grid[r][c].value);
	grid[r][c].value += diag;
      }
      else if ((up < left && r != 0) || c == 0){
	for (it = grid[r-1][c].path.begin(); it != grid[r-1][c].path.end(); it++){
	  grid[r][c].path.push_back(*it);
	}
	grid[r][c].path.push_back(grid[r][c].value);
	grid[r][c].value += up;
      }
      else{
	for (it = grid[r][c-1].path.begin(); it != grid[r][c-1].path.end(); it++){
	  grid[r][c].path.push_back(*it);
	}
	grid[r][c].path.push_back(grid[r][c].value);
	grid[r][c].value += left;
      }	
    }
  }
           
  cout << grid[n-1][n-1].value << endl;
  it = grid[n-1][n-1].path.begin();
  cout << *it;
  it++;
  for (; it != grid[n-1][n-1].path.end(); it++){
    cout << " " << *it;
  }
  cout << endl;

  /*
  for (int i = 0; i < n; i++){
    for (int j = 0; j < n; j++){
      cout <<setw(4)<< grid[i][j].value << " ";
    }
    cout << endl;
  }
  */
}