import java.util.*;

public class Naloga3 {

    private static int cost;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        //String type = args[0];

        int n = sc.nextInt(); sc.nextInt();
        cost = Integer.MAX_VALUE;
        int[][] adj = new int[n][n];
        int[][] adjt = new int[n][n];
        int[] visited = new int[n];
        Arrays.fill(visited, 0);
        int[] min = new int[n];
        Arrays.fill(min, Integer.MAX_VALUE);
        int[] path = new int[n];
        Arrays.fill(path, -1);
        int pi = 0;

        for (int i = 0; i < adj.length; i++) {
            for (int j = 0; j < adj[i].length; j++) {
                adj[i][j] = sc.nextInt();
                if (adj[i][j] != 0 && adj[i][j] < min[i]) min[i] = adj[i][j];
            }
        }

        Arrays.sort(min);

        visited[0] = 1;
        path[pi++] = 0;
        TSPBacktracking(adj, visited, 0, 0, path, pi, 0, min);

    }

    static int cnt = 0;

    private static void TSPBacktracking(int[][] adj, int[] visited, int node, int c, int[] path, int pi, int num, int[] min) {

        if (visited(visited)) {
            int cst = c + adj[path[path.length-1]][0];
            if (cst < cost) {
                cost = cst;
                System.out.print(cst + ":");
                for (Integer i : path) System.out.print(" " + i);
                System.out.println();
            }
        }

        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                path[pi++] = i;

                int cst = c + adj[node][i];
                int mp = 0;
                for (int k = 0; k < adj.length - num - 1; k++) mp += min[k];

                if (cst < cost - mp) {
                    TSPBacktracking(adj, visited, i, cst, path, pi, num + 1, min);
                    visited[i] = 0;
                    path[--pi] = -1;
                }
            }
        }
    }

    private static boolean visited(int[] v) {
        for (int i = 0; i < v.length; i++) if (v[i] == 0) return false;
        return true;
    }

}