馬計是嗚嗚物流公司的快遞員，他每天勤奮地運送貨物，只為手上的快遞工作可以盡快完成。
這天，他想要拓展業務，也就是幫公司內的其他員工規劃送貨路線！
這樣就能讓公司送更多的貨，拓展公司版圖，順便賺其他員工的小費。
馬計想要幫 $T$ 位員工規劃路線，每位員工 $E_i$ 需要配送 $p_i$ 個貨物，為了方便我們將貨物編號為 $1,\;2,\;...,\;p_i$。
馬計還勤奮地把所有簽收點之間的路記在紙上，其中 $r_{i,j,k}$ 代表員工 $E_i$ 從貨物 $j$ 的簽收點到貨物 $k$ 的簽收點的路長為 $r_{i,j,k}$，若 $r_{i,j,k}=-1$ 則代表員工 $E_i$ 的 $j, k$ 簽收點之間沒有路，但可經由其他簽收點間接到達。
緊接著就是最重要的問題—最短的貨物配送路線是甚麼呢？
由於這問題困擾馬計很久，因此他把這張記著所有路線資訊的紙給你，希望你可以幫他找到最短的路線，還叮囑你可以從任意地點出發配送貨物，
並且可以假定每位員工與第一個配送地點的距離為 $0$，但是每個簽收點只能到達一次。
聰明的你想到可以用程式解決這個問題，請你幫幫馬計吧！
第一行有一數 $T$，代表馬計想要幫忙 $T$ 位員工。
接下來有 $T$ 組輸入，每組之間會換行：
每組第一行有一數 $p_i$ 代表 $E_i$ 要配送的貨物數量。
每組第 $j+1$ 行，每行有 $p_i$ 個數以空白隔開，分別代表 $r_{i,j,1},\;r_{i,j,2},\;...,\;r_{i,j,p_i}$
其中 $1\leq j\leq p_i$。
對於每組輸入輸出兩行，每組之間要換行：
每組第一行輸出 $p_i$ 個以空白隔開的數字，代表配送貨物的順序。
每組第二行輸出這個配送順序的路徑長。
最短的配送順序有很多種，輸出任意一種即可。
2 5 0 9 2 7 9 9 0 10 2 6 2 10 0 6 -1 7 2 6 0 2 9 6 -1 2 0 5 0 6 6 -1 4 6 0 2 5 10 6 2 0 4 4 -1 5 4 0 7 4 10 4 7 0
3 1 5 4 2 15 4 2 3 5 1 15
$20\%$ 測資，$3\leq p_i\leq 10$
$60\%$ 測資，$3\leq p_i\leq 14$
$100\%$ 測資，$3\leq p_i\leq 18$
對於所有測資，$1\leq T\leq 5,\;-1\leq r_{i,j,k}\leq 40$，$1\leq i\leq T,\;1\leq j,k\leq p_i$
且 $r_{i,j,j}=0,\;r_{i,j,k}=r_{i,k,j}$。
對第一個範例測資來說，輸出路徑 $5,4,2,1,3$ 也正確，因為它的路徑也是最短的 $15$。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||