题面翻译

曾经存在的高桥王国有N个城市，城市与城市之间用长度为整数的无向道路连接。

现有一考古学家找到了一张N×N的表A，这张表代表了这N座城市两两之间的最短路。即表中的第u行第v列的值代表了从城市u到v的最短路长度。

问能否根据这张表，求出高桥王国的最小道路长度总和。

输入格式

第一行：N 下面是大小为N×N的表A

输出格式

一个整数，表示最小道路长度总和。如果无解，输出−1

数据范围与约定

• 1 <= N <= 300
• 当 i != j 时，1 <= 表A中第i行第j列的值 == 表A中第j行第i列的值 <= 10^9
• 表A中第i行第i列的值为0

样例1解释

• 从城市1到城市2有长度为1的直接道路
• 从城市2到城市3有长度为2的直接道路
• 从城市1到城市3无直接道路

样例2解释

从城市1走到城市2要走长度为1的道路，从城市2走到城市3要走长度为1的道路，所以从城市1到城市3要走的距离为2，但表中是3，所以无解。