描述

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

现在给定这张有向图每两个点之间的有向路径长度，对于所有满足 1 ≤ x,y,z ≤ n,x ≠y,y≠z 的有序数对（x,y,z），求它们 d（x,y,z）的和。

也就是对于每个 y，求除了 y之外，其余的所有点组成的有序点对 (x,z) 不经过 y 的最短路长度（不存在即为 -1）。

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

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

输出 输出一个整数表示答案。

输入样例 1

3 0 1 -1 100 0 2 -1 -1 0 输出样例 1

100 输入样例 2

4 0 1 -1 -1 -1 0 1 -1 -1 -1 0 1 1 -1 -1 0 输出样例 2

4