1277: 列车线路

卡卡西来到了一个叫“比特兰”的国家，“比特兰”是个很发达的国家，有着非常高科技的列车，和非常复杂的列车线路。具体来说，从理论上，我们可以假设这个国家的高科技列车可以不消耗时间的从 A 地瞬间转移到 B 地。同时， 铁路线路复杂到，每对城市之间都有列车连接。但是不幸的是，由于这种列车运行需要很多维护工作，所以每天只能发出一次。从 i 到 j 的列车(i≠j)会在 ti,j 时间发出（保证 ti,j 两两不同）。

如果有一条路径链接 A 和 B 两个城市，并且满足路径上的每⼀条边的发车时间单调递增（也就是说经过的每段铁路的发出时间都要大于上一段的，因为我们需要从上一段铁路换乘下一段铁路）。 现在“比特兰”的铁路局想要知道，一天之内，对于每一对 i 和 j，如果想要从 i 到达 j，最早多早能到达呢？

第一行一个整数 n。

接下来 n 行，每行 n 个整数。表示 ti,j。（i=j 时保证 ti,j=0，不算一条线路）

3
0 4 5
2 0 3
1 6 0

0 4 5
2 0 3
1 4 0