AT_arc083_b [ABC074D] Restoring Road Network

#### 题面翻译 曾经存在的高桥王国有N个城市，城市与城市之间用长度为正整数的无向道路连接。 现有一考古学家找到了一张N×N的表A，这张表代表了这N座城市两两之间的最短路。即表中的第u行第v列的值代表了从城市u到v的最短路长度。 问能否根据这张表，求出高桥王国的最小道路长度总和。

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

一个整数，表示最小道路长度总和。如果无解，输出−1 #### 数据范围与约定 - 1

### 制約 - $ 1≦N≦300 $ - $ i\ ≠\ j $ のとき、$ 1\ ≦\ A_{i,\ j}\ =\ A_{j,\ i}\ ≦\ 10^9 $ - $ A_{i,\ i}\ =\ 0 $ ### Sample Explanation 1 条件を満たす道路の構造は以下のとおりです。 - 都市 $ 1 $ と都市 $ 2 $ の間は長さ $ 1 $ の道路によって結ばれている。 - 都市 $ 2 $ と都市 $ 3 $ の間は長さ $ 2 $ の道路によって結ばれている。 - 都市 $ 3 $ と都市 $ 1 $ の間は道路で結ばれていない。 ### Sample Explanation 2 都市 $ 1 $ から都市 $ 2 $ へ、および都市 $ 2 $ から都市 $ 3 $ へそれぞれ距離 $ 1 $ で移動できることから、 都市 $ 1 $ から都市 $ 3 $ へは都市 $ 2 $ を経由することで距離 $ 2 $ で移動できることがわかります。 一方、都市 $ 1 $ と都市 $ 3 $ の間の最短距離は $ 3 $ でなければなりません。 よって条件を満たす道路の構造は存在しないことがわかります。