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

#include <stdio.h>
#define INFINITY 1<<24

int main(){
	unsigned int N,k,i,j,t;
	unsigned int a[500][500];
	scanf("%d",&N);
	for(i=0;i<N;i++)
		for(j=0;j<N;j++){
			scanf("%d",&t);
			if (t == 0)
				a[i][j] = INFINITY;
			else
				a[i][j] = t;
		}

		for(k=0;k<N;k++)
			for(i=0;i<N;i++)
				for(j=0;j<N;j++){
					unsigned int sum;
					//if ((a[i][k] < INFINITY)&&(a[k][j] < INFINITY))
						sum = (a[i][k] + a[k][j]);
					if ((a[i][j] == sum)||(!(a[i][j] < INFINITY))){
						a[i][j] = INFINITY;
						a[j][i] = INFINITY;
					} else
					if (a[i][j] > sum)
						a[i][j] = (a[i][k] + a[k][j]);
				}

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

	return 0;
}