题目描述

给定一张带权无向完全图，设点的编号为 1,2,3,4,5....n（以邻接矩阵的形式给出）。

计算依次拿走第 i个点后，剩余所有点到其他点的最短距离之和的总和（具体请看样例）。

输入格式

第一行包含一个整数 n。

接下来 n行，每行包含 n个空格隔开的整数，表示邻接矩阵，其中第 i行第 j

列的数字 a_ij表示点 i和点 j之间存在一条边，长度为 a_ij。

输出格式

一个整数，表示最短距离之和的总和。

样例

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

8

提示

1≤n≤500,

a_ii=0,

0<a_ij≤10 (i≠j)

拿走 1号点后，2,3,4号点构成一个等边三角形，每个点到其他两点的最短距离都为 1，所以所有点到其他点的最短距离之和的总和为 2+2+2=6。

拿走 1,2号点后，3,4号点之间存在一条边，边长为 1，所以所有点到其他点的最短距离之和的总和为 1+1=2。

拿走 1,2,3号点后，仅剩 1个点，不存在到其他点的最短距离。

拿走所有点后为空。最终结果为 6+2+0+0=8。