/*
TASK:oldmap
Lang:C
*/
#include<stdio.h>
#include<stdlib.h>
#define maxn 501
#define NO_RIB 1000001
struct h{
 int to;
 int dist;
 } ;
char p[maxn][maxn];
int a[maxn][maxn],n;
struct h heap[maxn];
int hlen;
char used[maxn];
/*int operator = (struct h &r,const struct h b)
{
r.dist=b.dist;
r.to=b.to;
return 0;
} */
void diikstra (int v)
{
int i;
hlen=2;
/*for(i=0;i<n;i++)
  used[i]=0;
used[v]=1; */
heap[1].to=0;
heap[1].dist=a[v][0];
for(i=0;i<n;i++)
  {
  heap[hlen].dist=a[v][i];
  heap[hlen].to=i;
  siftup(hlen);
  hlen++;
  }
hlen--;
for(i=0;i<=hlen;i++)
  pp(v);
}

int pp(int v)
{
struct h c;
c.dist=heap[hlen].dist;
c.to=heap[hlen].to;

int x,j,i;
j=heap[1].to;
a[v][j]=heap[1].dist;
//used[heap[1].to]=1;
heap[1]=heap[hlen];
hlen--;
x=2;
while(x<hlen)
  {
  if(heap[x+1].dist<heap[x].dist)x++;
  if(heap[x].dist<c.dist) heap[x/2]=heap[x];
  else break;
  x=x*2;
  }
heap[x/2]=c;
for(i=2;i<n;i++)
  {
  if(heap[i].dist>=a[v][j]+a[j][i])
    {
    p[v][heap[i].to]=1;
    heap[i].dist=a[v][j]+a[j][i];
    siftup(i);
    }
  if(heap[i].dist>=a[v][j]+a[j][i])
    {
    p[v][heap[i].to]=1;
    heap[i].dist=a[v][j]+a[j][i];
    siftup(i);
    }
  }
return 0;
}

int siftup(int i)
{
struct h c;
c.dist=heap[hlen].dist;
c.to=heap[hlen].to;
int x=hlen;
while(heap[x/2].dist>c.dist&&x>1)
  {
  heap[x]=heap[x/2];
  x=x/2;
  }
heap[x].dist=c.dist;
heap[x].to=c.to;
}

int main()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    {
    if(j!=i)
       p[i][j]=0;
    else
       p[i][j]=1;
    }
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    {
    scanf("%d",&a[i][j]);
    if(i==j)
      a[i][j]=NO_RIB;
    }
for(i=0;i<n;i++)
  diikstra(i);
for(i=0;i<n;i++)
  for(j=i+1;j<n;j++)
     if(p[i][j]==0)
        printf("%d %d %d\n",i+1,j+1,a[i][j]);
return 0;
}

