题目概述

• 时间限制：1s
• 空间限制：512MB

题目描述

我离开了组织
又成了孤身一尘
尝试，失败
尝试，再失败
然而却终于发现了什么
看似疯狂的世界
似乎还在变化着
我不清楚它会迎来什么
但我一定不要迷茫
因为我有了我自己的方向
向着中心
起航

---

终于，我决定了，在这个日趋疯狂的世界，用我自己的努力去寻找生命的希望。

然而，前方混乱的尘埃团却让我感到迷茫，而且一些尘埃团已经变得不能接近，不能作为我前进的中转站，我必须要找到一个最快最安全的到达中心的方向——

如今的关系早已不是最初那么简单，已经是一张复杂的有向图，为了找到最好的路线，我需要统计各种方案下的最短路和：
一共有 n 个尘埃团，编号从 1 到 n。定义 \(d(u,v,w)\)为从 u号点出发，严格不经过 v号点，最终到达 w号点的最短路径长度，如果不存在这样的路径，\(d(u,v,w)\) 的值为 −1。
定义路径和
\[P=\sum_{1<=x,y,z<=n \land x!=y \land y!=z} {d(x,y,z)}\]
请你求出P的值。

输入

第一行输入一个正整数 n
接下来输入 n 行，每行输入 n个整数。第 i行第 j个数 \(G(i,j)\)
表示从 i号点到 j号的有向路径长度。如果这个数为 −1，则表示不存在从 i号点出发到 j号点的路径。

输出

输出P值

样例

输入

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

输出

4

数据范围

\(4<=n<=300\)
\(-1<=G(i,j)<=10000\)
\(G(i,i)=0\)

数据分布

1-5 \(n<=20\)
6-10 \(n<=100\)
11-20 无特殊限制