Description

对于一张有向图，定义 $d(u,v,w)$ 为从 $u$ 号点出发，不经过 $v$ 号点，最终到达 $w$ 号点的最短路径长度。如果不存在这样的路径，$d(u,v,w)$ 的值为 $-1$。

你也可以认为 $d(u,v,w)$ 是删去 $v$ 点和其相关的边后，图中 $u$ 到 $w$ 的最短路。

现在给定这张有向图每两个点之间的有向边的长度（如果不存在连边则为 $-1$），对于所有满足 $1 \le x,y,z \le n, x \ne y, y \ne z$ 的有序数对 $(x,y,z)$，求它们 $d(x,y,z)$ 的和。

你可以借助样例一解释来理解上面这句话的意思。

Input Format

第一行输入一个正整数 $n$，表示该地区的点数。

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

Output Format

输出一个整数表示答案。

Sample

样例一输入

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

样例一输出

100

样例一解释说明

这张有向图中 1->2 的边长为 1，2->1 的边长为 100，2->3 的边长为 2。

所有的合法的 $x,y,z,d(x,y,z)$ 的值为：

$x$	$y$	$z$	$d(x,y,z)$
$2$	$1$	$2$	$0$
		$3$	$2$
$3$		$2$	$-1$
		$3$	$0$
$1$	$2$	$1$
		$3$	$-1$
$3$		$1$
		$3$	$0$
$1$	$3$	$1$
		$2$	$1$
$2$		$1$	$100$
		$2$	$0$

请注意 $x=z$ 时，$d(x,y,z)$ 为 $0$。

所有合法的 $d(x,y,z)$ 的和为 $100$。

样例二输入

4
0 1 -1 -1
-1 0 1 -1
-1 -1 0 1
1 -1 -1 0

样例二输出

4

样例三输入输出

见下发的选手目录。

Hint

对于所有数据，有 $3 \le n \le 300$，$-1 \leq G_{i,j} \leq 10000$，$G_{i,i} = 0$。

本题一共有 $10$ 个测试点，每个测试点 $10$ 分。

各个测试点的约束如下：

| 测试点编号 | $n \le$ | 特殊性质 |

| ---------- | ------- | -------- |

| $1$ | $3$ | 无 |

| $2$ | $3$ | 无 |

| $3$ | $10$ | 无 |

| $4$ | $10$ | 无 |

| $5$ | $50$ | 性质1 |

| $6$ | $50$ | 无 |

| $7$ | $50$ | 无 |

| $8$ | $300$ | 性质1 |

| $9$ | $300$ | 性质1 |

| $10$ | $300$ | 无 |

性质1：除了 $G_{i,i}=0$ 以外的所有边，边权相等且不为 $-1$。