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

#include <cstdio>
#include <cstdlib>

#define MAXN 600

using namespace std;

int g[MAXN][MAXN];
int c[MAXN][MAXN];
int used[MAXN];
int N;
int target, parent, result;
int prev[MAXN];

void read_input(void)
{
 int i, j;

 for(i=0; i<N; i++)
  used[i] = 0;

 scanf("%d", &N);
 for(i=0; i<N; i++)
  for(j=0; j<N; j++)
  {
   scanf("%d", &g[i][j]);
   c[i][j] = g[i][j];
  }
 return;
}

void cycle(int start, int end, int count)
{
 int temp=0;
 int oldprev;
 int nstart=start;
 if(!count) return;
// printf("%d %d\n", start, end);
 oldprev = prev[end];
 prev[end]=start;
 while(nstart!=end)
 {
  temp+=g[nstart][prev[nstart]];
  nstart = prev[nstart];
 }
 if(temp<=g[start][end])
  c[start][end]=0;
 else
  cycle(prev[start], start, count-1);
 prev[end]=oldprev;
}

void DFS(int node)
{
 for(int i=0; i<N; i++)
  if(g[node][i] && i!=prev[node])
   if(used[i])
    cycle(node, i, 500);
   else
   {
    used[i] = 1;
    prev[i] = node;
    DFS(i);
   }
}

int main()
{
 int i=0, j;
 read_input();
// for(i=0; i<N-1; i++)
  DFS(i);
 for(i=0; i<N; i++)
  for(j=i+1; j<N; j++)
   if(c[i][j])
    printf("%d %d %d\n", i+1, j+1, c[i][j]);
 return 0;
}

