时间限制：1秒　　内存限制：256M

---

【题目描述】

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

　　两个略有不同的 5*6 矩阵的最小路径如下。只有矩阵中最下面一行的数不同。右边矩阵的路径利用了第一行与最后一行相邻的性质。

【输入格式】

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

【输出格式】

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

【输入输出样例】

　Input

5 6
3 1 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 3 8 6 4

　Output

1 1 5 4 4 5
16

【数据限制】

　　对于 \(30\%\) 的数据，\(1≤M,N≤10\)。
　　对于 \(50\%\) 的数据，\(1≤M,N≤100\)。
　　对于 \(100\%\) 的数据，\(1≤M,N≤1000\)，矩阵的每个元素为 1..100 之间的数。

【来源】

　　Mr.he