题目描述

输入一个有向图的邻接矩阵格式，输出每对顶点间的最短路径长度

输入

输入第一行为n，表示下面是个n * n的矩阵，接下来就是n * n的矩阵形式，每个元素值都是整型，如果不能直接到，则是-1

输出

输出也是一个n * n的矩阵形式，每个元素的值为两个顶点间的最短路径值，如果到不了，则输出-1，最后一行的换行也输出

样例

3
0 1 3
2 0 5
3 2 0

0 1 3
2 0 5
3 2 0