/*
TASK:OLDMAP
LANG:C++
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define maxval 99999999
#define FOR(i,n) for(int i=0;i<n;i++)
#define maxn 501
struct type {
       int x,y,len;
       type() {}
       type(int _x,int _y,int _len) {
                x = _x;
                y = _y;
                len = _len;
       }
};
bool operator<(type a,type b) {
     return a.len > b.len;
}
std::priority_queue<type> q;
std::vector<std::pair<int,int> > v;
int A[maxn][maxn];
bool F[maxn][maxn];
bool B[maxn][maxn];
int n;
void init() {
     scanf("%d",&n);
     FOR(i,n) FOR(j,n) { 
              scanf("%d",&A[i][j]); 
              if(i<j) q.push(type(i,j,A[i][j]));
     }
     
     // purvite nai blizki 2 vurha !!!
     type top = q.top();
     q.pop();
     F[top.x][top.y] = 1;
     F[top.y][top.x] = 1;
     v.push_back(std::make_pair(top.x,top.y));
     
     top = q.top();
     q.pop();
     F[top.x][top.y] = 1;
     F[top.y][top.x] = 1;
     v.push_back(std::make_pair(top.x,top.y));
}
bool All() {
     if(q.empty()) return true;
     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()) {
        int vsize = v.size();
        FOR(i,vsize) printf("%d %d %d\n",v[i].first+1,v[i].second+1,A[v[i].first][v[i].second]);
        return;
     }   
     while(1) {
              type top;
              while(!q.empty()) {
                 top = q.top();
                 q.pop();
                 if(B[top.x][top.y] || B[top.y][top.x]) continue;
              }
              F[top.x][top.y] = F[top.y][top.x] = 1;
              v.push_back(std::make_pair(top.x,top.y));
              if(All()) {         
                 int vsize = v.size();
          FOR(i,vsize) printf("%d %d %d\n",v[i].first+1,v[i].second+1,A[v[i].first][v[i].second]);
                 return;
              }
     }
}
int main() {
    init();
    solve();
    scanf("%d",&n);
    return 0;
}
