城市交通路网

题目描述

城市编号1..N。费用矩阵表示有向道路，正数为费用，0表示无道路，对角线为0。求城市1到城市N的最少费用，并给出最短路径；如有多条最短路径，选顶点编号序列字典序最小的一条。

输入

第一行N，1≤N≤200；随后N行，每行N个整数，0≤w[i][j]≤10^9，对角线0。道路费用严格为正。

输出

无法到达时仅输出minlong=-1。否则第一行minlong=最少费用，第二行依次输出从1到N的路径顶点。N=1时费用0、路径为1。

输入样例

10
0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0

输出样例

minlong=19
1 3 5 8 10