/*
TASK:oldmap
LANG:C++
*/
#include <iostream>

using namespace std;

//ifstream cin( "oldmap.in" );
//ofstream cout( "oldmap.out" );

long int a[ 512 ][ 512 ];
bool used[ 512 ][ 512 ];
int pred[ 512 ];
int n;


void indata( )
{
 int i, j;

 cin >> n;
 for ( i=1; i<=n; i++ )
	 for ( j=1; j<=n; j++ )
	 {
		 cin >> a[ i ][ j ];
		 used[ i ][ j ] = false;
    }
}

int isused( int i, int j )
{
  if ( !used[ i ][ j ] )
	 return 1;
  return 0;
}

void dijkstra( int u )
{
  int i, j, k, mj, w;
  int x[ 512 ];
  long int d[ 512 ];
  int nue[ 512 ];

  for ( i=1; i<=n; i++ )
	  { x[ i ] = i; d[ i ] = 999999999; pred[ i ] = -1; }

	d[ u ] = 0;
	pred[ u ] = -1;
	nue[ u ] = 0;
  for ( k=n; k>=1; k-- )
  {
	 for ( mj=1, j=1; j<=k; j++ )
		 if ( d[ x[ mj ] ] > d[ x[ j ] ] )
			mj=j;
	i = x[ mj ];
	w = x[ mj ]; x[ mj ] = x[ k ]; x[ k ] = w;

	for ( j=1; j<=n; j++ )
		if ( i != j )
		if ( d[ j ] > d[ i ] + a[ i ][ j ] )
      {
		  d[ j ] = d[ i ] + a[ i ][ j ];
		  pred[ j ] = i;

		  if ( used[ i ][ j ] == true )
				nue[ j ] = nue[ i ];
		  else
			 	nue[ j ] = nue[ i ] + 1;
     }
   	else
      {
		  if ( ( d[ j ] == d[ i ] + a[ i ][ j ] ) && ( nue[ j ] > nue[ i ] + isused( i,j ) ) )
        {
			  pred[ j ] = i;
			  nue[ j ] = nue[ i ]  + isused( i,j );
        }
      }
  }
}


void solve( )
{
  int i, j, p, j1;

  for ( i=1; i<=n; i++ )
  {
	 dijkstra( i );

	 for ( j=1; j<=n; j++ )
		if ( i != j )
		{
		   j1 = j;
			p = pred[ j1 ];

			while ( p != -1 )
         {
			  used[ p ][ j1 ] = used[ j1 ][ p ] = true;
			  p = pred[ p ];
			  j1 = pred[ j1 ];
         }
		}
  }

  for ( i=1; i<=n; i++ )
	  for ( j=i+1; j<=n; j++ )
		  if ( used[ i ][ j ] )
			 cout << i << " " << j << " " << a[ i ][ j ] << endl;
}

int main( )
{
 	indata( );
	solve( );

	return 0;
}
