/*
TASK: OLDMAP
LANG: C
*/
#include<stdio.h>
#include<stdlib.h>

#define MAXN 512
#define MAXM 252144
#define INF 2000000000

typedef struct edge { int l,r,c; } edge;

int d[MAXN][MAXN],ec;
edge e[MAXM];

int cmp(const void *e1,const void *e2)
{
        return ((edge*)e1)->c-((edge*)e2)->c;
}

int main()
{
        int i,j,n,c;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        scanf("%d",&c);
                        if(i<j) { e[ec].l=i+1; e[ec].r=j+1; e[ec++].c=c; }
                        d[i+1][j+1]=INF;
                }
                d[i+1][i+1]=0;
        }
        qsort(e,ec,sizeof(e[0]),cmp);
        for(i=0;i<ec;i++)
        {
                if(d[e[i].l][e[i].r]==e[i].c) continue;
                printf("%d %d %d\n",e[i].l,e[i].r,e[i].c);
                d[e[i].l][e[i].r]=e[i].c;
                for(j=1;j<=n;j++)
                {
                        if(d[j][e[i].l]+e[i].c<d[j][e[i].r])
                        {
                                d[j][e[i].r]=d[e[i].r][j]=d[j][e[i].l]+e[i].c;
                        }
                        if(d[j][e[i].r]+e[i].c<d[j][e[i].l])
                        {
                                d[j][e[i].l]=d[e[i].l][j]=d[j][e[i].r]+e[i].c;
                        }
                }
        }
        return 0;
}

