题目描述

城市编号1至 $n$，给出城市间的道路长度。只能沿道路从编号小的城市前往编号大的城市。求从1到 $n$ 的最短距离。

输入格式

第一行 $n$，随后 $n$ 行，每行 $n$ 个非负整数，表示对称的距离矩阵；0表示没有道路，对角线为0。

输出格式

输出最短距离。

样例

2
0 5145
5145 0

5145

数据范围

$1\le n\le100$，道路长度为1至10000的整数。保证按规定方向可以从1到 $n$。