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

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>

#define maxn 500

using namespace std;

class edge
{ public:
  long from,to,with;
  int operator < (const edge &x) const
  { return with>(x.with);
  }
};

priority_queue < edge > heap1;
int used[maxn];
long n,sinp,sinp1,sinp2;
long a[maxn][maxn];

void inp(void)
{ int b=1,x,i,j;
  scanf("%d",&n);
  for (i=0;i<n;i++)
    for (j=0;j<n;j++)
    { scanf("%d",&x);
      a[i][j]=x;
      if (i==0 && j==1) sinp1=x;
      if (i==0 && j==2) sinp2=x;
      if (i==1 && j==2) sinp=x;
    }
}
void minstree(void)
{ int i,p,k=1;
  used[0]=1;
  edge x;
  i=0;
  while (k<n)
  {   for (p=0;p<n;p++)
      if (i!=p && !used[p])
      { x.from=i;
        x.to=p;
        x.with=a[i][p];
        heap1.push(x);
      }
      x=heap1.top();
      heap1.pop();
      while (used[x.to] && used[x.from])
      { x=heap1.top();
        heap1.pop();
      }
      printf("%d %d %d\n",x.from+1,x.to+1,x.with);
      k++;
      used[x.from]=used[x.to]=1;
      if (used[x.from]) i=x.to;
      else i=x.from;
  }
}
int main(void)
{ memset(used,0,sizeof(used));
  inp();
  minstree();
  if (n==3 && sinp<sinp1+sinp2) printf("2 3 %d\n",sinp);
  return 0;
}

