#include<iostream.h>
#include<fstream.h>

int main()
{
int C[20][20];
int n,i,j,k;

ifstream f("royfloyd.in");
ofstream g("royfloyd.out");

f>>n;

for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)	
		f>>C[i][j];
	
	// Algoritmul lui Roy-Floyd de determinare a drumurilor de cost minim intre 
	// oricare doua varfuri ale grafului orientat
	
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(C[i][k]+C[k][j]<C[i][j])
					C[i][j]=C[i][k]+C[k][j];
				
				
				g<<"Costurile minime:"<<endl;
				
				for(i=1;i<=n;i++)
				{
					for(j=1;j<=n;j++)
						g<<C[i][j]<<" ";
						g<<endl;
				}
				
				f.close();
				g.close();
				
				return 0;
				
				
}