#include<bits/stdc++.h>

using namespace std;

#define int long long int
#define PB   push_back
using pii = pair<int, int>;
using vi  = vector<int>;
using vvi = vector<vi>;
#define Endl "\n"
#define sixeof sizeof
#define NOT ~
static int tc = 0;
const int mxn = 1e6+2;
const int lgn = 20;
const int mod = (119<<23)+1;
// const int mod = 1e9+7;

int bigMod(int b, int p, const int mod) {
    int res = 1;
    b%=mod;
    while(p) {
        if(p&1) res = (res * b)%mod;
        b = (b * b)%mod;
        p/=2;
    }
    return res;
}
// a
// z
int mul(long long x, long long y) {
    x*=y;
    return (int)(x%mod);
}
int add(long long x, long long y) {
    x+=y;
    if(x>=mod) x-=mod;
    if(x<mod) x+=mod;
    return (int)x;
}
struct DSU {
    int n;
    vector<int>p, rnk;
    DSU(int n) {
        p = vector<int>(n+1, 0);
        rnk = vector<int>(n+1, 1);
        iota(begin(p), end(p), 0);
    }
    int find(int u) {
        return p[u]==u?u:find(p[u]);
    }
    int merge(int u, int v) {
        u = find(u);
        v = find(v);
        if(u^v) {
            if(rnk[u]<rnk[v]) u^=v, v = u^v, u = u^v;
            p[v] = u;
            rnk[u]+=rnk[v];
            return rnk[u];
        }
        return 0;
    }
};
const int N = 2e3+2;
int n;
int b[N][N], c[N][N];
int getH(int x, int y) {
    return (x-1)*n+y-1;
}
int get(int temp, int&x,  int&y) {
    x = temp/n+1;
    y = temp%n+1;
}
vector<int> g[N];
int root;
void dfs(int u, int p) {
    for(int &v: g[u]) {
        if(v^p) {
            c[root][v] = c[root][u]+1;
            dfs(v, u);
        }
    }
}
void solve() {
    if(!(cin >> n)) exit(0);
    vector<int> v;
    if(tc) cout << Endl;
    tc++;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cin >> b[i][j];
            if(i<j)
            v.push_back(getH(i, j));
        }
    }
    sort(begin(v), end(v), [&](int t2,  int t3) {
        int x, y, xp, yp;
        get(t2, x, y);
        get(t3, xp, yp);
        return (b[x][y]<b[xp][yp]);
    });
    vector<int> edges;
    DSU dsu(n);
    int nttken = 0;
    for(int i=0; i<v.size(); i++) {
        int x, y;
        get(v[i], x, y);
        if(dsu.merge(x, y)) {
            edges.push_back(v[i]);
            v[i] = -1;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        if(v[i]>=0) nttken = v[i];
    }
    for(int i=1; i<=n; i++) {
        root = i;
        c[i][i] = 0;
        dfs(i, i);
    }
    for(int i=0; i<v.size(); i++) {
        if(v[i]==-1) continue;
        int x, y;
        get(v[i], x, y);
        if(b[x][y]==c[x][y]) continue;
        int xp, yp;
        get(nttken,xp,yp);
        if(b[x][y]<b[xp][yp]) nttken = v[i];
    }
    edges.push_back(nttken);
    for(int i=0; i<n; i++) {
        int x, y;
        get(edges[i], x, y);
        cout <<x <<" "<<y<<" "<<b[x][y]<<Endl;
    }
    for(int i=1; i<=n; i++) g[i].clear();

}
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t, tc=1e8;
    while(tc--)
//    for(cin >> t; tc<=t; tc++)

    {
        // cout <<"Case "<<tc<<":\n";
//             cout << "Case #"<<tc<<": ";
        solve();
    }
}
// a