/*
TASK:oldmap
LANG:C
*/
#include <stdio.h>
#include <stdlib.h>

#define VBN (1000001)

typedef struct
{
  long l;
  short a, b;
} path;

short N;
long pc, dist[500][500];
path paths[125000];

int cmp(const void *a, const void *b)
{
  if(((path*)a)->l<((path*)b)->l)
    return -1;
  if(((path*)a)->l>((path*)b)->l)
    return 1;
  return 0;
}

void input(void)
{
  short x, y;
  pc=0;
  scanf("%hd", &N);
  for(x=0; x<N; x++)
    for(y=0; y<N; y++)
      {
        scanf("%ld", &paths[pc].l);
        if(y<x)
        {
          paths[pc].a=x;
          paths[pc].b=y;
          pc++;
        }
      }
}

int main(void)
{
  long i;
  short x, y;
  for(x=0; x<500; x++)
    for(y=0; y<500; y++)
      dist[x][y]=VBN;
  input();
  qsort(paths, pc, sizeof(path), cmp);
  for(i=0; i<pc; i++)
    if(paths[i].l<dist[paths[i].a][paths[i].b])
    {
      printf("%hd %hd %ld\n", paths[i].b+1, paths[i].a+1, paths[i].l);
      dist[paths[i].a][paths[i].b]=dist[paths[i].b][paths[i].a]=paths[i].l;
      for(x=0; x<N; x++)
      {
        if(dist[x][paths[i].a]>dist[x][paths[i].b]+paths[i].l)
          dist[x][paths[i].a]=dist[paths[i].a][x]=dist[x][paths[i].b]+paths[i].l;
        if(dist[x][paths[i].b]>dist[x][paths[i].a]+paths[i].l)
          dist[x][paths[i].b]=dist[paths[i].b][x]=dist[x][paths[i].a]+paths[i].l;
      }
    }
  return 0;
}

