该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】

有n个城市，编号1～n，有些城市之间有路相连，有些则没有，有路则会有一个距离。图9．12-1所示为一个含有11个城市的交通图，连线上的数(权)表示距离。现在规定只能从编号小的城市到编号大的城市。问：从编号为1的城市到编号为n的城市之间的最短距离是多少?

【输入格式】

第1行为n，表示城市数，n≤100。

下面的n行是一个n X n的邻接矩阵map[i，j]，其巾map[i，j]=0表示城市i和城市j之间没有路相连，否则为两者之间的距离。

【输出格式】

一行一个数，表示最短距离。数据保证一定可以从城市1到城市n。

【输入样例】

11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 6 3 0 0 0 0 0
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 0 0 0
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0

【输出样例】

13