/*
TASK:oldmap
LANG:C
*/
#include<stdio.h>
#define maxn 500
#define MAXVAL 10000000
int isused[maxn],N;
struct edge
{
int fr,to;
long dist;
};
int compare(const void *p,const void *q)
{return (*(struct edge *)p).dist-(*(struct edge *)p).dist;}
int check (int i,int j,long dist,long tn);
long a[maxn][maxn],b[maxn],nov[maxn][maxn];

struct edge c[maxn*maxn];
int main()
{
int i,j,t=-1;
scanf("%d",&N);
for(i=0;i<N;i++)
  for(j=0;j<N;j++)
  	{
    scanf("%ld",&a[i][j]);
    if(a[i][j]!=0)
    	{
      t++;
      c[t].fr=i;
    	c[t].to=j;
      c[t].dist=a[i][j];
      }
    }
qsort(c,t,sizeof(struct edge),compare);
for(i=0;i<N;i++)
	for(j=0;j<N;j++)
  	nov[i][j]=MAXVAL;
for(i=0;i<t;i++)
{
  if(nov[c[i].fr][c[i].to]==MAXVAL&&check(c[i].fr,c[i].to,c[i].dist,0)==0)
     {
     nov[c[i].fr][c[i].to]=c[i].dist;
     nov[c[i].to][c[i].fr]=c[i].dist;
     }
}
for(i=0;i<N;i++)
	for(j=i+1;j<N;j++)
  	if(nov[i][j]!=MAXVAL)
    	printf("%d %d %ld\n",i+1,j+1,nov[i][j]);
return 0;
}

int check (int i,int j,long dist,long tn)
{
int k,fl=0;
if(nov[i][j]!=MAXVAL&&tn+nov[i][j]==dist)
	return 1;
for(k=0;k<N;k++)
	if(nov[i][k]!=MAXVAL&&isused[k]==0&&nov[i][k]+tn<dist)
  	{
    isused[k]=1;
    fl=check(k,j,dist,tn+a[i][k]);
    isused[k]=0;
    if(fl==1)
    	break;
    }
return fl;
}

