#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#define INFINITY 1001

int * * royfloyd(int * * vertTab,int nrEdges);

int min(int a,int b);

int main()
{
 FILE * fpin,* fpout;
 fpin=fopen("royfloyd.in","r");
 fpout=fopen("royfloyd.out","w");	
	
 int nrEdges;
 fscanf(fpin,"%d",&nrEdges);
 
 int i,j,* * vertTab;
 vertTab=(int * *)calloc(nrEdges,sizeof(int *));
 for (i=0;i<nrEdges;i++)
  vertTab[i]=(int *)calloc(nrEdges,sizeof(int));
  
 for (i=0;i<nrEdges;i++)
  for (j=0;j<nrEdges;j++)
   fscanf(fpin,"%d",&vertTab[i][j]);
 fclose(fpin);
 
 int * * shPathsTab=royfloyd(vertTab,nrEdges);
 
 /*for (i=0;i<nrEdges;i++)
 {
  for (j=0;j<nrEdges;j++)
   printf("%d ",shPathsTab[i][j]);
  printf("\n");
 }*/
 
 for (i=0;i<nrEdges;i++)
 {
  for (j=0;j<nrEdges;j++)
   fprintf(fpout,"%d ",shPathsTab[i][j]);
  fprintf(fpout,"\n");
 }
 
 fclose(fpout);
 return 0;	
}

int * * royfloyd(int * * vertTab,int nrEdges)
{
 int i,j,k,* * shPathsTab;
 shPathsTab=(int * *)calloc(nrEdges,sizeof(int *));
 for (i=0;i<nrEdges;i++)
  shPathsTab[i]=(int *)calloc(nrEdges,sizeof(int));
  
 for (i=0;i<nrEdges;i++)
  for (j=0;j<nrEdges;j++)
   if (i==j) shPathsTab[i][j]=0;
    else if (vertTab[i][j]==0) shPathsTab[i][j]=INFINITY;
    else shPathsTab[i][j]=vertTab[i][j];
    
 for (k=0;k<nrEdges;k++)
  for (i=0;i<nrEdges;i++)
   for (j=0;j<nrEdges;j++)
    shPathsTab[i][j]=min(shPathsTab[i][j],shPathsTab[i][k]+shPathsTab[k][j]);
    
 return shPathsTab;
}

int min(int a,int b)
{
 if (a<b) return a;
 return b;	
}