/*
TASK:oldmap
LANG:C++
*/

#include <cstdio>
#include <algorithm>
#include <limits>

const int MAXN = 1 << 9;
const int MAXM = MAXN * MAXN;

const int MAXHLEN = MAXN * 2;

struct heap {
	int to;
    int dist;
    heap () {}
    heap (int tt, int dd) : to (tt), dist (dd) {}
};

const int infinity = std::numeric_limits <int>::max ();
heap h[MAXHLEN];
int hlen;
int idx[MAXN];
const int NOT_IN = -1;
const int POPPED = -2;


int N, N2;
int ma3x[MAXN][MAXN];

struct el {
	int to;
    int dist;
    int next;
    el () {}
    el (int tt, int nn, int dd) : to (tt), dist (dd), next (nn) {}
};

int vec[MAXN];
el buf[MAXM];
int bp;


void init () {
	int i;
	for (i = 1; i < N2; ++i)
    	h[i].dist = infinity;
    h[0].dist = -infinity;

    hlen = 1;
    for (i = 0; i < N; ++i)
    	idx[i] = NOT_IN;
}

void siftup (int to) {
	heap tomove = h[idx[to]];
    int p1 = idx[to], p2 = p1/2;

	while (h[p2].dist > tomove.dist) {
    	h[p1] = h[p2];
        idx[h[p2].to] = p1;

        p1 = p2;
        p2 /= 2;
    }

    h[p1] = tomove;
    idx[to] = p1;
}


void add (int to, int dist) {
	if (idx[to] == NOT_IN) {
        h[hlen] = heap (to, dist);
        idx[to] = hlen++;
    	siftup (to);
    } else if (idx[to] != POPPED && h[idx[to]].dist > dist) {
    	h[idx[to]].dist = dist;
        siftup (to);
    }
}


heap pop () {
	heap ret = h[1];
    idx[ret.to] = POPPED;
    heap tomove = h[--hlen];
    h[hlen].dist = infinity;

    if (hlen == 1)
    	return ret;

	int p1 = 1, p2 = 2;

    for (;;) {
		if (h[p2+1].dist < h[p2].dist)
        	++p2;
        if (h[p2].dist < tomove.dist) {
        	h[p1] = h[p2];
            idx[h[p2].to] = p1;

            p1 = p2;
            p2 *= 2;
        } else
        	break;
    }

    h[p1] = tomove;
    idx[tomove.to] = p1;

    return ret;
}

int dijkstra (int st, int fin) {
    static heap crnt;
    static int i;

	init ();
    add (st, 0);

    while (hlen > 1) {
    	crnt = pop ();
        if (crnt.to == fin)
        	return crnt.dist;

        for (i = vec[crnt.to]; i != -1; i = buf[i].next)
        	add (buf[i].to, buf[i].dist + crnt.dist);
    }
}



struct ts {
    int a;
    int b;
	int dist;
    ts () {}
    ts (int aa, int bb, int dd) : a (aa), b (bb), dist (dd) {}
};

ts vts[MAXN * MAXN / 2];
int vtsp;

int a[MAXN];

bool cmpd (const ts &a, const ts &b) {
	return (a.dist != b.dist ? a.dist < b.dist : a.a < b.a);
}

int main () {
	scanf ("%d", &N);
    N2 = N * 2;

    int i, j;
    for (i = 0; i < N; ++i)
    	for (j = 0; j < N; ++j) {
        	scanf ("%d", &ma3x[i][j]);
            if (i < j)
            	vts[vtsp++] = ts (i, j, ma3x[i][j]);
        }

    std::sort (vts, vts + vtsp, cmpd);
/*
    for (i = 0; i < vtsp; ++i)
    	printf ("%d %d %d\n", vts[i].a, vts[i].b, vts[i].dist);
*/

	int p, q;
    for (i = 0; i < N; ++i) vec[i] = -1;
    for (i = 0; i < N; ++i) a[i] = i;
	for (i = 0; i < vtsp; ++i) {
    	for (p = a[vts[i].a]; p != a[p]; p = a[p]) p = a[a[p]];
    	for (q = a[vts[i].b]; q != a[q]; q = a[q]) q = a[a[q]];

        if (p != q) {
        	a[p] = q;
            printf ("%d %d %d\n", vts[i].a + 1, vts[i].b + 1, vts[i].dist);

            buf[bp] = el (vts[i].b, vec[vts[i].a], vts[i].dist);
            vec[vts[i].a] = bp++;

            buf[bp] = el (vts[i].a, vec[vts[i].b], vts[i].dist);
            vec[vts[i].b] = bp++;
        } else {
        	if (dijkstra (vts[i].a, vts[i].b) > vts[i].dist) {
	            printf ("%d %d %d\n", vts[i].a + 1, vts[i].b + 1, vts[i].dist);

                buf[bp] = el (vts[i].b, vec[vts[i].a], vts[i].dist);
    	        vec[vts[i].a] = bp++;

            	buf[bp] = el (vts[i].a, vec[vts[i].b], vts[i].dist);
            	vec[vts[i].b] = bp++;
            }
        }
    }

	return 0;
}

