Description
著名的旅行推銷員問題(Travelling Salesman Problem)講述的是：
有n個城市，有一個推銷員要從其中某一個城市出發，走遍所有的城市(同一城市只能路過一次)後再回到他出發的城市，
並求最短的路線(也就是求一個最短的哈密頓迴路(Hamiltonian circuit))。
今天我們將它簡化為：
1.給定一m*n的矩陣，請你找出一條最小權重的路徑。一條路徑可由column 1 上的任一點出發，
經過一些移動後抵達終點，終點可以是column n上的任一個點。
2.The firstrow & last row(row 1 &row n)視為相連(也就是row 1 往上走會走到row n，反之亦然)。
以上規則類似於 Unidirectional TSP
不同的是，這次推銷員騎了一匹馬來當代步工具，因此推銷員每次移動都是走"日"字(詳見fig.a)，
並且不會往回走(請參考fig.Sample)。
(fig.a) (fig.Sample)
Input
有多組測資，請以EOF為輸入終止條件。
每組測資第一行有兩個整數n,m，代表這組測資有n rows, m columns(1<=n<=20,1<=m<=200)。
再來有n行，每一行有m個整數，代表矩陣的元素(0<=Mij<=2^15)。
Output
對於每組測資輸出兩行：第一行請印出該路徑，第二行則請印出該路徑權重。
若有兩條權重相同的路徑，請輸出字典序較小者。(優先比較row number，次序比較col number)