You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

小 B 将会告诉小 A ，这 N 个城市之间最短路径的长度（ ​n​×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)。

输出格式

输出最短的道路总长度。

输入样例

3
0 1 3
1 0 2
3 2 0​

输出样例

3

数据范围

对于29%的数据，1≤​N​≤300；

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