/*
TASK:OLDMAP
LANG:C++
*/

#include <stdio.h>
#define min(a,b) (a < b ? a : b)
#define MAX 10000001

long d[501][501];
int n,i,j;

long long MIN = 0, cur = 0;

void dfs(int i, int j) {

if (i == j) {
   cur += d[i][j];
   MIN = min(MIN,cur);
   return;
   } else {
     for (int x=1; x<=n; x++)
       if (d[i][x]) {
          long tmp = d[i][x];
          d[i][x] = 0; d[x][i] = 0;
          cur += tmp;
          dfs(x,j);
          cur -= tmp;
          d[i][x] = tmp; d[x][i] = tmp;
          }
     }

}

int main() {

//freopen("maps.inp","r",stdin);
scanf("%d", &n);

for (i=1; i<=n; i++)
  for (j=1; j<=n; j++)
    scanf("%ld", &d[i][j]);

for (i=1; i<=n-1; i++)
  for (j=i+1; j<=n; j++) {
     long tmp = d[i][j];
     d[i][j] = 0; d[j][i] = 0; cur = 0; MIN = MAX*MAX;
     dfs(i,j);
     if (tmp < MIN) {
        d[i][j] = tmp;
        d[j][i] = tmp;
        }
     }

for (int i=1; i<=n-1; i++)
  for (int j=i+1; j<=n; j++)
    if (d[i][j]) printf("%ld %ld %ld\n", i, j, d[i][j]);
  

return 0;
}

