/*
TASK:OLDMAP
LANG:C++
*/
#include <stdio.h>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define maxn 501
int A[maxn][maxn];
std::set< std::pair<int,int> > s;
int n;
int fsize = 0;
void init() {
     scanf("%d",&n);
     FOR(i,n) FOR(j,n) scanf("%d",&A[i][j]);
     for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
           s.insert(std::make_pair(i,j));
}
void floyd() {
     FOR(k,n) 
        FOR(i,n) if(i!=k)
           FOR(j,n) 
              if(i!=j && k!=j && A[i][k]+A[k][j]==A[i][j]) {
                      s.erase(std::make_pair(i,j));
              }
     for(std::set<std::pair<int,int> >::iterator it=s.begin(); it!=s.end(); ++it) 
         printf("%d %d %d\n",(*it).first+1,(*it).second+1,A[(*it).first][(*it).second]);
}
int main() {
    init();
    floyd();
    return 0;
}
