/*
TASK:oldmap
LANG:C
*/
#include<stdio.h>

#define MAXN	1024
#define INF		1000000000000

int N;
long long dist[MAXN][MAXN],adj[MAXN][MAXN],min[MAXN],d[MAXN][MAXN];

void solve()
{
	int i,j;
	long long dmin;
	for(i=0;i<N;i++)
	{
		dmin=INF;min[N+1]=0;
		for(j=0;j<N;j++)
		{
			if(!dist[i][j])continue;
			if(dist[i][j]<=dmin)
			{
				min[min[N+1]++]=j;dmin=dist[i][j];
			}
		}
		for(j=0;j<N;j++)
		{
			adj[i][min[j]]=dmin;
			adj[min[j]][i]=dmin;
		}
	}
}

void floyd()
{
	int i,j,k;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		{
			if(!adj[i][j])
				d[i][j]=INF;
			else
				d[i][j]=adj[i][j];
		}
	for(k=0;k<N;k++)
		for(i=0;i<N;i++)
			for(j=0;j<N;j++)
			{
				if(i==j)continue;
				if(d[i][j] > d[i][k]+adj[k][j])
					d[i][j]=d[i][k]+adj[k][j];
			}
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			if(d[i][j]>dist[i][j])
			{
				adj[i][j]=dist[i][j];
				adj[j][i]=dist[j][i];
			}
	for(i=0;i<N;i++)
		for(j=i+1;j<N;j++)
			if(adj[i][j])
				printf("%d %d %lld\n",i+1,j+1,adj[i][j]);
}

int main()
{
	int i,j;
	scanf("%d",&N);
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			scanf("%lld",&dist[i][j]);
	solve();
	floyd();
	return 0;
}