/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package gridtsp;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 *
 * @author Michael Dunham and Keane
 */
public class GridTSP {

    static int row;
    static int col;
    static int[][] graph;
    static int[][] path;
    static PrintWriter out;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws FileNotFoundException {
        // TODO code application logic here
        Scanner in = new Scanner(new File("tsp.in"));
        out = new PrintWriter(new File("tsp.out"));
        while (in.hasNext()) {
            row = in.nextInt();
            col = in.nextInt();
            graph = new int[row][col];
            path = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    graph[i][j] = in.nextInt();

                }
            }
            for (int i = 0; i < row; i++) {
                path[i][0] = graph[i][0];
            }

            for (int j = 1; j < col; j++) {
                for (int i = 0; i < row; i++) {
                    path[i][j] = lowest(i, j);
                }
            }
//            System.out.println("Graph:");
//            for (int i = 0; i < row; i++) {
//                for (int j = 0; j < col; j++) {
//                    System.out.print(graph[i][j] + " ");
//
//
//                }
//                System.out.println("");
//            }
//            System.out.println("Path:");
//            for (int i = 0; i < row; i++) {
//                for (int j = 0; j < col; j++) {
//                    System.out.print(path[i][j] + " ");
//
//
//                }
//                System.out.println("");
//            }

            int lowestCost = Integer.MAX_VALUE;
            for (int j = 0; j < row; j++) {
                lowestCost = Math.min(path[j][col - 1], lowestCost);
            }

            out.println(findPath(path));
            out.println(lowestCost);

        }
        out.close();

    }

    public static String findPath(int[][] in) {
        String output = "";
        int lowestCost = Integer.MAX_VALUE;
        for (int j = 0; j < row; j++) {
            lowestCost = Math.min(path[j][col - 1], lowestCost);
        }
        int iCoor = 0;
        for (int j = 0; j < row; j++) {
            if (lowestCost == path[j][col - 1]) {
                iCoor = j;
                break;
            }
        }
       // System.out.println("iCoor = " + iCoor);
        char neighbor = lowestNeighbor(iCoor, col - 1);
       // System.out.println("neighbor = " + neighbor);
        int k = iCoor;

        if (neighbor == 'u') {
            if (iCoor == 0) {
                k = row - 1;

            } else {
                k = iCoor - 1;
            }

        } else if (neighbor == 'l') {
            k = iCoor;

        } else {
            
            if (iCoor == row - 1) {
                k = 0;

            } else {
                
                k = k + 1;
            }

        }
      //  System.out.println("k= " + k);
        output = "" + (iCoor + 1);

        for (int j = col - 2; j >= 0; j--) {
            if (j == 0) {
                output = (k + 1) + " " + output;
            } else {
                output = (k + 1) + " " + output;
                neighbor = lowestNeighbor(k, j);
                if (neighbor == 'u') {
                    if (k == 0) {
                        k = row - 1;

                    } else {
                        k = k - 1;
                    }

                } else if (neighbor == 'l') {
                    k = k;

                } else if (neighbor == 'd') {
                    if (k == row - 1) {
                        k = 0;
                    } else {
                        k = k + 1;
                    }

                }

            }
        }

        return output;
    }

    public static int lowest(int i, int j) {
        int up, left, down;

        if (i == 0) {
            up = path[row - 1][j - 1] + graph[i][j];
        } else {
            up = path[i - 1][j - 1] + graph[i][j];
        }
        left = path[i][j - 1] + graph[i][j];
        if (i == row - 1) {
            down = path[0][j - 1] + graph[i][j];
        } else {
            down = path[i + 1][j - 1] + graph[i][j];
        }
        //System.out.println("Up: " + up + " Left: " + left + " Down: " + down);
        return Math.min(up, Math.min(down, left));
    }

    public static char lowestNeighbor(int i, int j) {
        int up, left, down;
        
        if (i == 0) {
            up = path[row - 1][j - 1];
        } else {
            up = path[i - 1][j - 1];
        }
        
        left = path[i][j - 1];
        if (i == row - 1) {
            down = path[0][j - 1];
        } else {
            down = path[i + 1][j - 1];
        }

        int min = Math.min(up, Math.min(down, left));
        if(i == row-1 && min == down){
            return 'd';
        }
        else if (up == min && i != 0) {
             return 'u';
        } 
        else if (left == min) {
            return 'l';
        } else if (down == min){
            
            return 'd';
        }
        else if (up ==  min && i == 0){
            return 'u';
        }
        else {
            return 'x';
        }
    }
}