Description

【问题描述】
有如下所示的交通路线图，边上数值表示该道路的长度，现要求出从1号地点到达7号地点的最短的路径长度是多少，并输出该长度。(道路长度小于等于0表示没有边直接相连，无法直接到达)。

Input

Output

Sample Input

7
0 5 22 0 0 0 0 
5 0 0 31 0 23 0
22 0 0 10 9 0 0
0 31 10 0 11 54 0
0 0 9 11 0 0 12
0 23 0 54 0 0 8
0 0 0 0 12 8 0

Sample Output

36

Source/Category