/*
TASK: oldmap
LANG: C++
*/

#include <stdio.h>
long long N;
long long a[505][505];

void input ()
{ int i,k;
  long long x;
  scanf("%lld",&N);
  for (i=1;i<=N;i++)
    for (k=1;k<=N;k++)
     { scanf("%lld",&a[i][k]);
       if (a[i][k]==0) a[i][k]=1000005;
     }
}

void floid ()
{ int i,j,k;
  for (k=1;k<=N;k++)
   for (i=1;i<=N;i++)
    for (j=1;j<=N;j++)
      if (a[i][j]>a[i][k]+a[k][j])
	  a[i][j]=a[i][k]+a[k][j];
  for (i=1;i<=N;i++)
    a[i][i]=500000005;
}

void solve ()
{ int i,j,k,l=0;
  floid();
  for (i=1;i<=N;i++)
     for (j=i+1;j<=N;j++)
       { for (k=1;k<=N;k++)
	   if (a[i][j]==a[k][i]+a[j][k]) { l=1; break; }
	 if (l==0) printf("%d %d %lld\n",i,j,a[i][j]);
	   else l=0;
    }
}

int main ()
{
  input();
  solve();
  return 0;
}
        


