/*
TASK:oldmap
LANG:C++
*/
#include<iostream>
using namespace std;

#define maxn 500
#define inf 1000001;

unsigned long long n,a[maxn][maxn];
bool nsp[maxn][maxn];
unsigned long long d[maxn][maxn];
void Dijkstra()
{
 int s;
 for(s=0;s<n;s++)
 {
  bool used[maxn];
  int i;
  for(i=0;i<n;i++)
  {
    d[s][i]=a[s][i];
    if(d[s][i]==0)d[s][i]=inf;
    used[i]=false;
  }
  used[s]=true;
  while(1)
  {
    int mi=-1;
    unsigned long long md=inf;
    for(i=0;i<n;i++)
    {
      if(!used[i] && d[s][i]<md)
        {
          md=d[s][i];mi=i;
        };
    }
    if(mi==-1)break;
    used[mi]=1;
    for(i=0;i<n;i++)
     if(!used[i] && ((a[mi][i]+d[s][mi])<=d[s][i]))
     {
       //cout<<s<<"->"<<mi<<"->"<<i<<endl;
       //printf("%d->%d->%d\n",s,mi,i);
       if(d[s][i]==(a[mi][i]+d[s][mi])){nsp[i][s]=1;nsp[s][i]=1;};
       d[s][i]=a[mi][i]+d[s][mi];
     };
  }
 }
};



int main()
{
  cin>>n;
  int i,j;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      cin>>a[i][j];
  Dijkstra();
  for(i=0;i<(n-1);i++)
    for(j=i+1;j<n;j++)
    if(nsp[i][j]==0)
         cout<<i+1<<" "<<j+1<<" "<<d[i][j]<<endl;
  return 0;
}

