题目描述

有 $\red{n}$ 个 城市，从$\red{1}$到$\red{n}$给他们编号，它们之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，每条路还有一个花费$\red{c(i)}$，表示通过第i条边需要花费$\red{c(i)}$的时间。

求任意两点间的最快路径

输入格式

第一行一个整数$\red{n}$，表示有多少个城市和多少条道路。

接下来$n$行，每行$n$个整数

第$\red{i+1}$行第$\red{j}$个数$x$表示从$\red{i}$到$\red{j}$有一条花费为$x$的边。（第$\red{i+1}$行第$\red{i}$个数为$\red{0}$）

输出格式

$\red n$行，每行$\red n$个整数

第$\red i$行第$\red j$个数表示从$\red i$到$\red j$最少需要多少时间。（第$\red i$行第$\red i$个数为$\red{ 0 }$）

样例

输入样例

4
0 487 569 408 
705 0 306 357 
95 222 0 618 
961 401 688 0

输出数据

0 487 569 408 
401 0 306 357 
95 222 0 503 
783 401 688 0

数据范围与提示

$\red{ 100\%}$的数据，$\red{1\le n\le 500}$

$\red{ 0\le m\le n*(n-1) }$