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

typedef struct
        {
        int b;
        int e;
        int l;
        }reb;
int a[501][501];
int n;
int main()
    {
    int i,j,k;
    //input
    //freopen("oldmap.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i!=n;i++)
       for(j=0;j!=n;j++)
          scanf("%d",&a[i][j]);
    //solve
    for(k=0;k!=n;k++)
       for(i=0;i!=n;i++)
         for(j=0;j!=n;j++)
            {
            if((i!=j)&&(i!=k)&&(j!=k))
               if(a[i][j]==a[i][k]+a[k][j])
                  {
                  a[i][j]=0;
                  a[j][i]=0;
                  }
            }
    //output
    for(i=0;i!=n;i++)
         for(j=0;j!=i;j++)
             {
             if(a[i][j]>0)
                {
                printf("%d %d %d\n",j+1,i+1,a[i][j]);
                }
             }
    return 0;
    }

