猜道路

题目限制

1500 ms 256 M

题目描述

$N$ 个城市（编号 $1$ 到 $N$ ）间的道路是双向的，小 $B$ 知道整个路网的情况，而小 $A$ 不知道，于是他们一起来做一个游戏。

小 $B$ 将会告诉小 $A$ ，这 $N$ 个城市之间最短路径的长度（ $n\times n$ 的表格 ），由小 $A$ 来猜城市间的道路究竟是什么样的。

小 $A$ 不需要猜中每一条道路的长度，只需要告诉小 $B$ ，在满足小 $B$ 提供的数据下，这些道路的总长度最小是多少。

如果不存在满足条件的路网，则输出 $-1$ 。

输入格式

第一行输入一个数N，表示城市个数。（1≤N≤300） 之后N行，每行N个数，其中第i行第j个数A(i,j)表示城市i到城市j的最短路长度。保证A(i,i)=0, A(i,j)=A(j,i)。

输出格式

输出最短的道路总长度。

数据范围

对于40%的数据，$1 \le N \le 10$；

对于100%的数据，$1 \le N \le 300, 1 \le A(i,j) \le 10^9, A(i,i) = 0$。

输入样例

3
0 1 3
1 0 2
3 2 0

输出样例

3