题目描述

有 $n$ 个城市，编号 $1 \sim n$，有些城市之间有路相连，有些则没有，有路则会有一个距离。图所示为一个含有 11 个城市的交通图，连线上的数（权）表示距离。

现在规定只能从编号小的城市到编号大的城市。问：从编号为 1 的城市到编号为 $n$ 的城市之间的最短距离是多少？

输入格式

第 1 行：一个整数 $n$，表示城市数。

下面的 $n$ 行：是一个 $n \times 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

数据范围

$n \leq 100$