D. 单项TSP

给定一个M行、N列的数字矩阵，你需要写一个程序计算一条从左到右走过矩阵且权和最小的路径。一条路径可以从第一列的任意位置出发，到达第N列的任意位置。每一步为从第i列走到第i+1列的相邻行（水平移动或沿45度斜线移动）。第一行和最后一行看作是相邻的，即你应当把这个矩阵看成是一个卷起来的圆筒。如下为合法的走法：  　　　　　　　　　　　　　　　　  　　路径的权和为所有经过的N个方格中整数的和。

两个略有不同的5*6矩阵的最小路径如下。只有矩阵中最下面一行的数不同。右边矩阵的路径利用了第一行与最后一行相邻的性质。  下图是两个矩阵和对应的最优路线（唯一的区别是最后一行）

第一行为两个整数M和N，分别表示矩阵的行数和列数。  　　接下来的M行，每行N个正整数，其中第i行第j列的整数表示矩阵的第i行第j列的元素。

第一行为最小权和的路径，第二行为该路径的权和。路径由N个整数组成（相邻整数间用一个空格分开），表示路径经过的行号。如果权和最小的路径不止一条，输出字典序最小的一条。

对于30%的数据有：N,M<=10；  对于50%的数据有：N，M<=100;  对于100%的数据有：N,M<=1000，矩阵的每个元素为1..100之间的数;