/*
TASK:oldmap
LANG:C++
*/
#include <stdio.h>
#include <algorithm>
#include <queue>

#define IN "oldmap.in"
#define OUT "oldmap.out"

#define MAXN 512
#define A input[i].a
#define B input[i].b
#define P input[i].p


using namespace std;

int N;
int Free=1;

typedef struct edge1 {
        int a,b;
        long long p;

        edge1 () {a=0;b=0;p=0;}
        edge1 (int aa,int bb,long long pp) {
             a = aa;
             b = bb;
             p = pp;
        }

        bool operator <(const edge1 &h) const {
             if (a == h.a)
                if (b < h.b) return true;
                else return false;
             else
                if (a < h.a) return true;
                else return false;
        }
};

typedef struct edge2 {
        int a,b;
        long long p;

        edge2 () {a=0;b=0;p=0;}
        edge2 (int aa,int bb,long long pp) {
             a = aa;
             b = bb;
             p = pp;
        }

        bool operator <(const edge2 &h) const {
             if (p == h.p)
                if (a == h.a)
                   if (b < h.b) return true;
                   else return false;
                else
                   if (a < h.a) return true;
                   else return false;
             else
                if (p < h.p) return true;
                else return false;
        }
};

typedef struct node {
        int v;
        long long p;
        node (){v=0;p=0;}
        node (int vv,long long pp) {
             v = vv;
             p = pp;
        }
        bool operator <(const node &h) const {
             if (p == h.p)
                if (v > h.v) return true;
                else return false;
             else
                if (p > h.p) return true;
                else return false;
        }
};

vector <edge1> ans;
vector <node> ar[MAXN];
edge2 input[MAXN*MAXN];
long long d[MAXN];

long long get (int a,int b) {
    memset(d,31,sizeof(d));
    priority_queue<node> q;

    q.push(node(a,0));
    d[a]=0;

    node p;

    while (!q.empty()) {
          p = q.top();
          q.pop();

          if (d[p.v] != p.p) continue;
          if (p.v == b) return p.p;

          for (int i=0; i<ar[p.v].size(); i++) {
              d[ar[p.v][i].v] <?= p.p+ar[p.v][i].p;
              q.push(node(ar[p.v][i].v,p.p+ar[p.v][i].p));
          }
    }
    return d[b];
}

int main () {
//    freopen(IN,"r",stdin);
//    freopen(OUT,"w",stdout);

    scanf("%d",&N);
    long long p;
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            scanf("%lld",&p);
            if (i<=j) continue;
            input[Free].a=i;
            input[Free].b=j;
            input[Free].p=p;
            Free++;
        }
    }

    Free--;
    
    sort(&input[1],&input[1]+Free);

    for (int i=1; i<=Free; i++) {
        if (get(A,B) > P) {
           ar[A].push_back(node(B,P));
           ar[B].push_back(node(A,P));
           ans.push_back(edge1(B,A,P));
        }
    }

    sort(ans.begin(),ans.end());

    for (int i=0; i<ans.size(); i++) {
        printf("%d %d %lld\n",ans[i].a,ans[i].b,ans[i].p);
    }
    return 0;
}
