2256: 城市连接

Memory Limit:128 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:173 Solved:64

Description

天网恢恢,疏而不漏,经过上一次的抓捕,OI总部终于获取了怪盗的特征!现在,我们需要在基德再次来之前就把他的特征送到超级大牛的手上,可惜超级大牛不在总部.所以飞过海必须尽快把资料送到大牛家里.已知OI总部到大牛家中间有n-2个城城市,为了尽快达到目的地,飞过海通过水晶球(够先进吧)了解到OI总部到大牛家的路线图,图上显示了n个城之间的连接距离。 可是飞过海很忙,需要请你来帮忙写个程序.

Input

第一行  n    第二行到第n+1  行    每行  n个数字    (第i+1行,表示  第i个城市与其他城市之间的连接关系  0  表示不连接  其他数字表示连接的距离  ) 

Output

第1行  n个用空格间隔的整数  表示所选的线路    第2行  一个数字  最短距离

Sample Input Copy

7
0 3 5 0 0 0 0
0 0 0 7 8 6 0
0 0 0 0 4 5 0
0 0 0 0 0 0 4
0 0 0 0 0 0 7
0 0 0 0 0 0 6
0 0 0 0 0 0 0

Sample Output Copy

1 2 4 7
14

HINT

n<=1000

加入题单

算法标签: