#include<fstream.h>
int a[102][102],t[102][102],n;
void cit()
{
	ifstream fin("royfloyd.in");
	fin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			fin>>a[i][j];
	fin.close();
}
void init_a()
{
	/*Initializam matricea de adiacenta
a[i][j]=1, daca exista [i,j];
		0, daca i=j;
		5001(infinit), daca nu exista [i,j] si i!=j */
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]==0)
				a[i][j]=5001;
	for(i=1;i<=n;i++)
		a[i][i]=0;
}
void constr_a_t()
{
	/* Modificam matricea a a i a[i][j]=lungimea lantului minim intre i si j
	iar t[i][j]=nod intermediar pe un lant de lungime minima intre i si j */
	int k,i,j;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(a[i][k]+a[k][j]<a[i][j])
				{
					a[i][j]=a[i][k]+a[k][j];
					t[i][j]=k;
				}
}
ofstream fout("royfloyd.out");
void lant(int i,int j)
{
	//Afiseaza lantul de lungime minima dintre i si j, fara i si j
	int k;
	k=t[i][j];
	if(k!=0)
	{
		lant(i,k);
		fout<<k<<" ";
		lant(k,j);
	}
}
void afis()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			fout<<i<<" ";
			lant(i,j);
			fout<<j<<'\n';
		}
	fout.close();
}
int main()
{
	cit();
	init_a();
	constr_a_t();
	afis();
	return 0;
}