#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define LEFT 0
#define UP 1
#define DIAG 2 //diagonal

int min(int left, int diag, int up)
{
	int tempVar = left;
	if(up < left){ tempVar = up; }
	if(diag < tempVar){ tempVar = diag; }
	return tempVar;
}

int main()
{
	int i, j, gridSize, tempNum;
	vector< vector< int > > campus;
	vector< vector< int > > campus2;
	vector< vector< int > > path;
	vector<int> tempVec, tempVec2, tempVec3;
	stack<int> printPath;

	while(1)
	{
		cin >> gridSize;

		if(gridSize == 0){ break; }

		for(i = 0; i < gridSize+1; i++)
		{
			for(j = 0; j < gridSize+1; j++)
			{
				if(j == 0 || i == 0)
				{
					tempVec.push_back(0);
					tempVec2.push_back(3);
					tempVec3.push_back(0);
				} else
				{
					cin >> tempNum;
					tempVec.push_back(tempNum);
					tempVec2.push_back(3);
					tempVec3.push_back(0);
				}
			}
			campus.push_back(tempVec);
			path.push_back(tempVec2);
			campus2.push_back(tempVec3);
			tempVec.clear();
			tempVec2.clear();
			tempVec3.clear();
		}

		for(i = 1; i < gridSize+1; i++)
		{
			for(j = 1; j < gridSize+1; j++)
			{
				if(i == 1){
					if(j == 1){ campus2[i][j] = campus[i][j]; }
					else { campus2[i][j] = campus2[i][j-1] + campus[i][j]; }
				} else { 
					if(j == 1){ campus2[i][j] = campus2[i-1][j] + campus[i][j]; }
					else { campus2[i][j] = min(campus2[i][j-1], campus2[i-1][j-1], campus2[i-1][j]) + campus[i][j]; }
				}

				if(campus2[i][j] == campus2[i][j-1] + campus[i][j]){ path[i][j] = LEFT; }
				else if(campus2[i][j] == campus2[i-1][j] + campus[i][j]){ path[i][j] = UP; }
				else if(campus2[i][j] == campus2[i-1][j-1] + campus[i][j]){ path[i][j] = DIAG; }
			}
		}

		cout << campus2[gridSize][gridSize] << endl;

		i = gridSize;
		j = gridSize;

		while(i != 0 && j != 0)
		{
			printPath.push(campus[i][j]);
			if(path[i][j] == LEFT){ j--; }
			else if(path[i][j] == UP){ i--; }
			else if(path[i][j] == DIAG){ i--; j--; }
			//else if(path[i][j] == ROOT){ break; }
		}

		while(!printPath.empty())
		{ 
			cout << printPath.top(); 
			printPath.pop(); 
			if(!printPath.empty())
			{ 
				cout << " "; 
			} else 
			{
				break;
			}
		}
		cout << endl;

		/*for(i = 0; i < gridSize+1; i++){
			for(j = 0; j < gridSize+1; j++){
				cout << path[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;*/

		campus.clear();
		campus2.clear();
		path.clear();
	}

	return 0;
}