说明

给出一个边长为n的邻接矩阵，求第1号点到第n号点的最短路径的长度。

输入格式

第一行包括一个整数n (1 <= n <= 1000), 表示邻接矩阵的边长(即点的个数)

接下来n行, 每行n个数a1, a2, a3 ... , 分别表示所对应行列编号的路径长度。(0 <= ai <= 100)

输出格式

输出数据只有一行，包括一个整数，表示最短路径的长度。

样例

3
0 1 3
1 0 1
3 1 0

2

提示

给出的矩阵一定是一个对称矩阵, 且行列相等的位置均为0