/*------------------------------------------------------------------------------
 * problem015.c: Anti-Squirrel Hunt
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <limits.h>

/*------------------------------------------------------------------------------
 * Constants 
**----------------------------------------------------------------------------*/

#define NMAX_SQUARES 100

enum 
{
    WEST,
    NORTH,
    NORTHWEST
};

/*------------------------------------------------------------------------------
 * Global Variables
**----------------------------------------------------------------------------*/

int G[NMAX_SQUARES + 1][NMAX_SQUARES + 1]; // Grid
int S[NMAX_SQUARES + 1][NMAX_SQUARES + 1]; // Squirrel Table
int M[NMAX_SQUARES + 1][NMAX_SQUARES + 1]; // Move Table

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static void 
read_grid(int n)
{
    int r, c;

    memset(G, 0, sizeof(int) * (NMAX_SQUARES + 1) * (NMAX_SQUARES + 1));

    for (r = 1; r <= n; r++) 
	for (c = 1; c <= n; c++)
	    scanf("%d", &(G[r][c]));
}

/*----------------------------------------------------------------------------*/

inline int
min(const int a, const int b, const int c)
{
    int t = ((a < b) ? a : b);
    return ((t < c) ? t : c);
}

/*----------------------------------------------------------------------------*/

static void
print_table(int **T, int n)
{
    int r, c;
    
    for (r = 1; r <= n; r++)  {
	for (c = 1; c <= n; c++)
	    printf("%02d ", T[r][c]);
	putchar('\n');
    }
}

/*----------------------------------------------------------------------------*/
    
static void
compute_tables(int n)
{
    int r, c, m;
    
    S[0][0] = 0;
    for (r = 0; r <= n; r++) 
	for (c = 0; c <= n; c++)
	    if (r || c) S[r][c] = INT_MAX;

    for (r = 1; r <= n; r++) {
	for (c = 1; c <= n; c++) {
	    m = min(S[r][c - 1], S[r - 1][c - 1], S[r - 1][c]);

	    if (m == S[r][c - 1])
		M[r][c] = WEST;
	    else if (m == S[r - 1][c])
		M[r][c] = NORTH;
	    else
		M[r][c] = NORTHWEST;

	    S[r][c] = m + G[r][c];
	}
    }
}

/*----------------------------------------------------------------------------*/

static void
print_path(int n)
{
    int  p[NMAX_SQUARES * NMAX_SQUARES];
    int *fp;
    int  r, c;

    fp = p;
    r  = c = n;
    while (r > 0 && c > 0) {
	*fp++ = G[r][c];

	switch (M[r][c]) {
	    case WEST:	c--; break;
	    case NORTH: r--; break;
	    case NORTHWEST: r--; c--; break;
	}
    }
    fp--;

    printf("%d", *fp--);
    while (fp >= p)
	printf(" %d", *fp--);
    putchar('\n');
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    int n;

    while (scanf("%d", &n) != EOF) {
	if (n == 0) break;

	read_grid(n);
	compute_tables(n);

	printf("%d\n", S[n][n]);
	print_path(n);
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=cpp
**----------------------------------------------------------------------------*/