/*
TASK:OLDMAP
LANG:C++
*/
#include <stdio.h>
#include <string.h>
#define maxval 99999999
#define FOR(i,n) for(int i=0;i<n;i++)
#define maxn 501
int A[maxn][maxn];
bool F[maxn][maxn];
bool B[maxn][maxn];
int n;
void init() {
     scanf("%d",&n);
     int minn1,minn2;
     minn1 = minn2 = maxval;
     int v1,v2,v3,v4;
     v1 = v2 = v3 = v4 = -1;
     FOR(i,n) FOR(j,n) { 
              scanf("%d",&A[i][j]); 
              if(i<j) {
                      if(A[i][j]<minn1) {
                         minn2 = minn1;
                         v3 = v1;
                         v4 = v2;
                         minn1 = A[i][j];
                         v1 = i;
                         v2 = j;              
                     }
                     if(A[i][j]<minn2) {
                         minn2 = A[i][j];
                         v3 = i;
                         v4 = j;
                     }
              }
     }
     F[v1][v2] = F[v2][v1] = 1;
     F[v3][v4] = F[v4][v3] = 1;
}
bool All() {
     memset(B,0,sizeof B);
     FOR(i,n) FOR(j,n) B[i][j]=F[i][j];
     FOR(k,n) FOR(i,n) if(F[i][k] && i!=k) FOR(j,n) if(F[j][k] && j!=k && j!=i && !F[i][j]) {
              if(A[i][k] + A[k][j]==A[i][j]) {
                 B[i][j] = B[j][i] = 1;
              }
     }
     FOR(i,n) for(int j=i+1;j<n;j++) if(!B[i][j]) return false;
     return true;
}
void solve() {
     if(All()) {
        FOR(i,n) for(int j=i+1;j<n;j++) if(F[i][j]) 
           printf("%d %d %d\n",i,j,A[i][j]);
        return;
     }   
     while(1) {
              int nx,ny;
              nx = ny = -1;
              int minval = maxval;
              FOR(i,n) for(int j=i+1;j<n;j++) if(!F[i][j] && !B[i][j]) {
                 if(minval>A[i][j]) {
                                    nx = i;
                                    ny = j;
                                    minval = A[i][j];
                 }
              }
              F[nx][ny] = F[ny][nx] = 1;
              if(All()) {         
                 FOR(i,n) for(int j=i+1;j<n;j++) if(F[i][j]) 
                 printf("%d %d %d\n",i+1,j+1,A[i][j]);
                 return;
              }
     }
}
int main() {
    init();
    solve();
    scanf("%d",&n);
    return 0;
}
