你有一个包含 $n$ 个点的单向完全图，已知所有路径的长度。设 $D(i,j,k)$ 表示不能经过编号为 $k$ 的点，从 $i$ 到 $j$ 的最短路的长度。
现在出题人希望你求出 $ans$
\begin{equation} ans=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}D(i,j,k) \end{equation}
特别的，当 $i=k$ 或 $j=k$ 时，$D(i,j,k)=0$
输入格式
第一行包含一个正整数 $n$
接下来 $n$ 行，每行 $n$ 个非负整数
其中第 $i$ 行第 $j$ 个数 $d_{i,j}$，表示点 $i$ 到点 $j$ 连有一条长度为 $d_{i,j}$ 的有向边
特别的，保证对于任意 $i \in [1,n]$，存在 $d_{i,i}=0$
输出格式
一个整数，表示你求出的 $ans$ 的值
样例一
input
4
0 109 112 8
55 0 192 63
70 120 0 92
143 83 3 0input
1741样例二
见样例数据下载
样例三
见样例数据下载
样例四
见样例数据下载
限制与约定
对于 $10\texttt{%}$ 的数据，保证 $n = 4$
对于 $40\texttt{%}$ 的数据，保证 $n = 10$
对于 $60\texttt{%}$ 的数据，保证 $n = 100$
对于 $100\texttt{%}$ 的数据，保证 $n = 200, d_{i,j} \leq 200$
时间限制：$1\texttt{s}$
空间限制：$256\texttt{MB}$
