说明

下图表示城市之间的网络路线，线段上的数字表示网络延迟，单向通行由A(修远家)->E(DotA游戏服务器)。求A(修远家)->E(DotA游戏服务器)的最小延迟。

输入格式

第一行一个整数n，n不超过20，表示城市的数目。 此后的n行，每行n个整数。第x行y列的整数表示从第x台城市到第y城市的网络延迟。

'输出格式

输出从第1个城市出发到第n个城市的最短路径长度及最短路径。

输入数据 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

输出数据 1

minlong=19
1 3 5 8 10

提示

听说修远家里换了移动网络,移动千兆,DotA不能233