import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

/**
 * Created by Jonathan Nilsfors on 22/09/14.
 */
public class Main {

    public static void main(String[] args) {
        int rows, cols;
        int matrix[][] = new int[0][];

        if (args.length < 1 || args.length > 1) {
            System.out.println("Wrong argument. Supply a text file.");
            return;
        }

        BufferedReader br = null;
        try {
            br = new BufferedReader(new FileReader(args[0]));
        } catch (FileNotFoundException e) {
            System.out.println("File not found.");
            return;
        }

        try {

            String line;

            while ((line = br.readLine()) != null) {
                rows = Integer.parseInt(line.substring(0, line.indexOf(" ")).trim());
                cols = Integer.parseInt(line.substring(line.indexOf(" "), line.length()).trim());

                System.out.println("\nInput: ");
                System.out.print("rows: " + rows + " ");
                System.out.println("cols: " + cols);

                matrix = new int[rows][cols];

                for (int i = 0; i < matrix.length; i++) {
                    String[] parts = br.readLine().split(" ");
                    int[] n1 = new int[parts.length];
                    for(int n = 0; n < parts.length; n++) {
                        n1[n] = Integer.parseInt(parts[n].trim());
                        System.out.print(n1[n] + " ");
                    }
                    System.out.println("");
                    matrix[i] = n1;
                }
                System.out.println("\nOutput: ");

                System.out.println(shortestPathWrapper(matrix, rows - 1, cols - 1));
            }

        } catch (IOException e) {
            System.out.println("IO error");
            return;
        }
        finally {
            try {
                br.close();
            } catch (IOException e) {
                System.out.println("Error closing file.");
                return;
            }
        }
    }

    public static int shortestPathWrapper(int[][] matrix, int rows, int columns){
        int min = Integer.MAX_VALUE;
        int[][] memo = new int[rows+1][columns+1];
        for (int i = 0; i < memo.length; i++) {
            for(int n = 0; n < memo[i].length; n++) {
                memo[i][n] = Integer.MAX_VALUE;
            }
        }
        for(int i = 0; i <= rows; i++){
            min = Math.min(min, shortestPath(matrix, i, rows, columns, 0, memo));
        }
        int[] path = new int[columns+1];
        int start = Integer.MAX_VALUE;
        for (int i = 0; i < memo.length; i++) {
           if(memo[i][0] == min)
               path[0] = i;
        }
        for(int i = 1; i <= columns; i++){
            path[i] = Math.min(Math.min(memo[path[i] - 1 < 0 ? rows : path[i] - 1][i+1],memo[path[i]][i+1]),
                    memo[path[i] + 1 > rows ? 0 : path[i] + 1][i+1]);
        }
        for(int i = 0; i < path.length; i++){
            System.out.print(path[i] + " ");
        }
        return min;
    }


    public static int shortestPath(int[][] matrix, int currentRow, int rows, int columns, int currentCol, int[][] memo) {
        if(memo[currentRow][currentCol] != Integer.MAX_VALUE){
            return memo[currentRow][currentCol];
        }
        if (columns == currentCol) {
            return memo[currentRow][currentCol] = matrix[currentRow][currentCol];
        } else {
                int up = shortestPath(matrix, currentRow - 1 < 0 ? rows : currentRow - 1, rows, columns, currentCol + 1, memo);
                int mid = shortestPath(matrix, currentRow, rows, columns, currentCol + 1, memo);
                int down = shortestPath(matrix, currentRow + 1 > rows ? 0 : currentRow + 1, rows, columns, currentCol + 1, memo);
            return memo[currentRow][currentCol] = matrix[currentRow][currentCol] + Math.min(Math.min(up,mid), down);
        }

    }
}