一条路径的费用为矩阵中被访问过的单元格中的整数和。

　　

　　如上图的最小费用路径。

　　输入格式（TSP.IN）：
　　输入文件包含若干组矩阵描述，每组矩阵描述的第一行为矩阵的行列数M，N，然后M行为矩阵中的整数（每行N个）。输入以0 0表示M，N为结束。

　　输出格式（TSP.OUT）：
　　对于每组数据输出两行，第一行为其中一条最小费用的路径。第二行为费用。

　　示例输入：

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

　　样例输出：

　　1 2 3 4 4 5
　　16
　　1 2 1 5 4 5
　　11
　　1 1
　　19