#include<stdio.h>
#define infile "royfloyd.in"
#define outfile "royfloyd.out"
#define nmax 101
int m[nmax][nmax]; //matricea in care citim, si in care apoi facem algoritmul
int n; //numarul de noduri

void citire(int m[nmax][nmax], int *n)
	{
	int i,j;
	scanf("%d\n",n);
	for(i=1;i<=*n;i++)
		for(j=1;j<=*n;j++)
			scanf("%d",&m[i][j]);
	}

void floyd(int m[nmax][nmax], int n)
	{
	int i,j,k;
	for(k=1;k<=n;k++) //luam fiecare nod intermediar
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(m[i][k] && m[k][j] && (m[i][j]>m[i][k]+m[k][j] || !m[i][j])) //daca putem ajunge de la nodul i la nodul j prin nodul k cu un cost mai mic
					m[i][j]=m[i][k]+m[k][j]; //salvam costul
	for(i=1;i<=n;i++) m[i][i]=0; //punem 0 pe diagonala principala :P
	}

void afisare(int m[nmax][nmax], int n)
	{
	int i,j;
	for(i=1;i<=n;printf("\n"),i++)
		for(j=1;j<=n;j++)
			printf("%d ",m[i][j]);
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(m,&n); //citim
floyd(m,n); //facem matricea de cost minim intre noduri
afisare(m,n); //afisem matricea de cost minim

fclose(stdin);
fclose(stdout);
return 0;
}