/*
TASK:oldmap
LANG:C++
*/
#include <stdio.h>
unsigned long a[501][501]={0},r[501][501];
int k,n,f[501];

void inp(void)
{int i,j;
 scanf("%d",&n);
 for(i=1;i<=n;i++)
  for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
}

void ari(int u)
{int i,j;long p;

do
{
f[u]=1;
for(i=1;i<=n;i++)
   if(f[i]==0)
  {p=r[k][u]+a[u][i];
   if (p<r[k][i]) r[k][i]=p;
   }
 i=1;
 while(f[i]&&i<=n) i++;
 if(i<=n) {
j=i;
p=i;
for(i=j+1;i<=n;i++)
if(r[k][i]<r[k][p]&&f[i]==0) p=i;
u=p;
}
else u=0;
} while(u);
}

void inic(void)
{int i,j;
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++) r[i][j]=2000000000;
 for(i=1;i<=n;i++)
  for (j=1;j<=n;j++) if(a[i][j]==0) a[i][j]=200000000;
}
void outp(void)
{int i,j;
for(i=1;i<=n;i++)
 for(j=i+1;j<=n;j++) if(r[i][j]) printf("%d %d %d\n",i,j,r[i][j]);
}


int main(void)
{int i,j;
inp();
inic();
for(k=1;k<=n;k++) {r[k][k]=0;for(i=1;i<=n;i++) f[i]=0;ari(k);}
outp();
return 0;
}
