AT_arc083_b [ABC074D] Restoring Road Network

在曾经存在的高桥王国中，有 $N$ 座城市，其中一些城市对之间通过双向道路连接。 已知该王国的道路网络满足以下条件： - 人们只能通过道路在城市之间通行。任意两座城市之间都可以互相到达，必要时可以经过其他城市。 - 不同道路的长度可能不同，但所有道路的长度都是正整数。 考古学家 Snuke 在高桥王国的遗迹中发现了一个 $N$ 行 $N$ 列的表格 $A$。他认为，这张表格记录了王国中各城市之间沿道路行驶的最短距离。 请判断是否存在一个道路网络，使得对于任意 $u$ 和 $v$，表格 $A$ 中第 $u$ 行第 $v$ 列的整数 $A_{u,v}$，恰好等于从城市 $u$ 到城市 $v$ 的最短路径长度。 如果存在这样的道路网络，求所有道路长度之和的最小可能值。

第一行输入一个整数 $N$。 接下来 $N$ 行，每行输入 $N$ 个整数，其中第 $i$ 行第 $j$ 个整数为 $A_{i,j}$。

如果不存在满足条件的道路网络，输出 `-1`。 否则，输出所有道路长度之和的最小可能值。

**样例 #1 解释** 以下道路网络满足条件： - 城市 $1$ 与城市 $2$ 之间有一条长度为 $1$ 的道路。 - 城市 $2$ 与城市 $3$ 之间有一条长度为 $2$ 的道路。 - 城市 $3$ 与城市 $1$ 之间没有直接连接的道路。 **样例 #2 解释** 由于城市 $1$ 到城市 $2$ 存在一条长度为 $1$ 的路径，城市 $2$ 到城市 $3$ 也存在一条长度为 $1$ 的路径，因此城市 $1$ 到城市 $3$ 存在一条长度为 $2$ 的路径。 然而，根据表格，城市 $1$ 到城市 $3$ 的最短距离必须为 $3$。因此，不存在满足条件的道路网络。 **数据范围** - $1\le N\le 300$。 - 当 $i\ne j$ 时，$1\le A_{i,j}=A_{j,i}\le 10^9$。 - $A_{i,i}=0$。