/*
TASK:oldmap
LANG:C
*/
#include<stdio.h>
#define MAXN 510
#define MAX 10000000
#define MIN(a,b) (((a)<(b))?(a):(b))

void output();
void input();
void dfs(int v, int val);

int m[MAXN][MAXN]={0};
int d[MAXN][MAXN]={0};
int mx[MAXN][MAXN]={0};
int used[MAXN]={0};

int n;


void sort(int l, int r, int ind);
void input();



int main()
{
input();
dfs(0,0);
output();
return 0;
}




void dfs(int v, int val)
{
int i;

for(i=0;i<n;i++)
 if(!used[d[v][i]]&&m[v][i])
  {
  mx[v][i]=mx[i][v]=MIN(m[v][i]-val,m[v][i]);
  used[i]=1;
  dfs(d[v][i],val+m[i][v]);
  used[i]=0;
  }
}


void output()
{
int i,j;

for(i=0;i<n;i++)
 for(j=i+1;j<n;j++)
  if(mx[i][j])
   printf("%d %d %d\n",i+1,j+1,mx[i][j]);
}

 



void input()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
 for(j=0;j<n;j++)
  {
  scanf("%d",&m[i][j]);
  d[i][j]=j;
  }

for(i=0;i<n;i++) sort(0,n-1,i);
used[0]=1;
}



void sort(int l, int r, int ind)
{
int t;
int i,j;
int x=m[ind][(l+r)/2];

i=l; j=r;
while(i<j)
 {
 while(m[ind][i]<x) i++;
 while(m[ind][j]>x) j--;
 if(i<=j)
  {
  t=m[ind][i];
  m[ind][i]=m[ind][j];
  m[ind][j]=t;
  t=d[ind][i];
  d[ind][i]=d[ind][j];
  d[ind][j]=t;
  i++; j--;
  }
 }
if(i<r)
 sort(i,r,ind);
if(l<j)
 sort(l,j,ind);
}

  
  

