//roy-floyd 15.11.2011
#include<iostream>
#include<fstream>
using namespace std;
int n,v[101][101]; //v=matricea costurilor
void citire()
{
	ifstream fin("royfloyd.in");
	fin>>n;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			fin>>v[i][j];
	fin.close();
}
void roy_floyd()
{
	for (int k=1;k<=n;k++) //pt fiecare nod k
		for (int i=1;i<=n;++i) //pt fiecare muchie (i,j)
			for (int j=1;j<=n;++j) 
				if (v[i][k] && v[k][j] //daca exista (i,k) si (k,j)
					&& (v[i][j]>v[i][k]+v[k][j] || !v[i][j]) //si exista un drum mai bun de la i la j prin k, sau nu exista (i,j)
					&& i!=j) 
						v[i][j]=v[i][k]+v[k][j]; //atunci se poate ajunge mai repede de la i la j prin k
}
void scriere()
{
	ofstream fout("royfloyd.out");
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;j++)
			fout<<v[i][j]<<' ';
		fout<<'\n';
	}
	fout.close();
}
int main ()
{
	citire();
	roy_floyd();
	scriere();
	return 0;
}