#include <stdio.h>
  FILE *inputfile;
  FILE *outputfile;
int i,j,t,m,n;
    int diag[100];
int v[100][100],u[100][100],d[100][100],
    l[100][100],r[100][100],c[100][100],
    v1[100][100],u1[100][100],d1[100][100],
    l1[100][100],r1[100][100],c1[100][100];
char filename[10], dummy;
out(){
    printf(" t= %d\n", t);
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++) printf("%3d", c[i][j]); 
      for(j=1;j<=n;j++) fprintf(outputfile, "%3d", c[i][j]); 
       printf("\n");
       fprintf(outputfile, "\n");
    }
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++) {
        printf("  * %3d =>   ", l[i][j]); 
        fprintf(outputfile, "  * %3d =>   ", l[i][j]); 
      } 
      printf("\n");
      fprintf(outputfile, "\n");
      for(j=1;j<=n;j++) {
        printf("%3d %3d %3d  ", d[i][j], v[i][j], u[i][j]);
        fprintf(outputfile, "%3d %3d %3d  ", d[i][j], v[i][j], u[i][j]);
      } 
      printf("\n");
      fprintf(outputfile, "\n");
      for(j=1;j<=n;j++) {
        printf("  <=%3d   *  ", r[i][j]);
        fprintf(outputfile, "  <=%3d   *  ", r[i][j]);
      } 
      printf("\n");
      printf("\n");
      fprintf(outputfile, "\n");
      fprintf(outputfile, "\n");
    }
    getchar();
}
main(){
  scanf("%s",filename);
  inputfile=fopen(filename, "r");
  outputfile=fopen("meshout","w");
  scanf("%d",&n); getchar();
  for(i=1;i<= n;i++){ 
    for(j=1;j<=n;j++) { fscanf(inputfile,"%d",&v[i][j]); printf("%4d", v[i][j]);}
    printf("\n");
  }
  for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++){
    c[i][j]=0; u[i][j]=99; l[i][j]=99; d[i][j]=99; r[i][j]=99;
    c1[i][j]=0; u1[i][j]=99; l1[i][j]=99; d1[i][j]=99; r1[i][j]=99;
  }
  for(t=0;t<=5*n-5;t++){
    if(t % 3 == 0) c[t/3 + 1][t/3 + 1]=t/3 + 1;
    out();
    for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++){
     if((i>0)&&(c[i-1][j]==j)&&(i>j))  {c1[i][j]=c[i-1][j]; c1[i-1][j]=0;} //else
     if((i<n+1)&&(c[i+1][j]==j)&&(i<j)){c1[i][j]=c[i+1][j]; c1[i+1][j]=0;} //else
     if((j>0)&&(c[i][j-1]==i)&&(i<j))  {c1[i][j]=c[i][j-1]; c1[i][j-1]=0;} //else
     if((j<n+1)&&(c[i][j+1]==i)&&(i>j)){c1[i][j]=c[i][j+1]; c1[i][j+1]=0;}
   }

    for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++){
     if(c1[i][j]==i){
       if(i!=j){u1[i][j]=v[i][j]; d1[i][j]=v[i][j]; }
     } else{ 
     u1[i][j]=u[i-1][j]; d1[i][j]=d[i+1][j];}

     if(c1[i][j]==j){
       if(i!=j){l1[i][j]=v[i][j]; r1[i][j]=v[i][j]; }
     } else { 
     l1[i][j]=l[i][j-1]; r1[i][j]=r[i][j+1];}

     if(u[i-1][j]+l[i][j-1]<v[i][j])v1[i][j]=u[i-1][j]+l[i][j-1];
     else 
     if(u[i-1][j]+r[i][j+1]<v[i][j])v1[i][j]=u[i-1][j]+r[i][j+1];
     else 
     if(d[i+1][j]+l[i][j-1]<v[i][j])v1[i][j]=d[i+1][j]+l[i][j-1];
     else 
     if(d[i+1][j]+r[i][j+1]<v[i][j])v1[i][j]=d[i+1][j]+r[i][j+1];
     else v1[i][j]=v[i][j];
    }
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++) {
        c[i][j]=c1[i][j]; u[i][j]=u1[i][j]; d[i][j]=d1[i][j]; l[i][j]=l1[i][j];
        r[i][j]=r1[i][j]; v[i][j]=v1[i][j];
    }

  } /* t */
    printf(" result= \n");
    fprintf(outputfile, " result= \n");
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++) 
        {
        printf("%3d", v[i][j]); 
        fprintf(outputfile, "%3d", v[i][j]); 
        }
       printf("\n");
       fprintf(outputfile, "\n");
    }
}