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

#include <cstdio>
using namespace std;

int N,top=0,res[512][3],path[512];

struct node { int to; int teg; node* next; };

node* mat[512];

void readf()
{
        int i,j,a;
        node* tp;
        scanf("%d",&N);
        for(i=1;i<=N;i++) mat[i]=new node;
        for(i=1;i<=N;i++)
        {
           tp=mat[i];
           for(j=1;j<=N;j++)
           {
            scanf("%d",&a);
            if(a){
                   tp->next=new node; tp=tp->next;
                   tp->to=j; tp->teg=a;
                  }
           }
           tp->next=0;
         }
}

int bfs(int i,int to)
{
        int queue[512],used[512];
        int begQ,endQ,ii;
        for(ii=0;ii<=N;ii++) path[ii]=used[ii]=0;
        used[i]=1;
        queue[begQ=0]=i; endQ=1;
        while(begQ<endQ)
        {
                for(node* l=mat[queue[begQ]]->next;l;l=l->next)
                   if(!used[l->to]){
                                    used[l->to]=1;
                                    queue[endQ++]=l->to;
                                    path[l->to]=path[queue[begQ]]+l->teg;
                                    if(l->to==to) { return path[l->to]; }
                   }
                begQ++;
        }
}

void solve()
{
        int i;
        node* hj,*tmp,*hj2;
        for(i=1;i<=N;i++)
           for(hj=mat[i];hj->next;hj=hj->next)
              if((hj->next->to)>i)
              {
                    tmp=hj->next; hj->next=hj->next->next;
                    if(bfs(i,tmp->to)>tmp->teg){
                        res[top][1]=tmp->to;
                        res[top][2]=tmp->teg;
                        res[top][0]=i;
                        top++;
                    }
                    hj->next=tmp;
              }
}

void writef()
{
        int i;
        for(i=0;i<top;i++)
           printf("%d %d %d\n",res[i][0],res[i][1],res[i][2]);
}

int main()
{
        readf(); solve(); writef();
        return 0;
}
