对于一张有向图，定义 $d(u,v,w)$ 为从 $u$ 号点出发，不经过 $v$ 号点，最终到达 $w$ 号点的最短路径长度，如果不存在这样的路径，$d(u,v,w)$ 的值为 $-1$。
现在给定有向图中每两个点之间的有向边长度，求对于所有满足 $1\le x,y,z\le n(x\neq y,y\neq z)$ 的有序数对 $(x,y,z)$，求它们 $d(x,y,z)$ 的和。
也就是求对于每个 $y$，求除了 $y$ 之外，其余的所有点组成的有序点对 $(x,z)$ 不经过 $y$ 的最短路长度之和（不存在即为 $-1$）。

第一行输入一个正整数 $n$，表示点数。
接下来输入 $n$ 行，每行输入 $n$ 个整数，第 $i$ 行第 $j$ 个数 $G_{i,j}$ 表示从 $i$ 号点到 $j$ 号点的有向边长度，如果这个数为 $-1$，则表示不存在从 $i$ 号点到 $j$ 号点的有向路径。

输出一个整数表示答案。

3
0 1 -1
100 0 2
-1 -1 0

100