# include <iostream>
# include <fstream>

# define INF 10000

void read_data ( std :: istream & , int & ) ;
void read_matrix ( std :: istream & , int **, int ) ;
void print_matrix ( std :: ostream & , int ** , int ) ;
void free_matrix ( int ** , int ) ;
void royfloyd ( std :: ostream & , int ** , int ) ;

int main () {

	std :: ifstream f ("royfloyd.in" ) ;
	std :: ofstream g ("royfloyd.out" ) ;
	
	int N ;
	int **values = NULL ;
	
	read_data ( f , N ) ;

	values = new int * [N] ;
	for ( int i = 0 ; i < N ; i ++ ) {
	
		values[i] = new int [N] ;
	
	}

	read_matrix ( f , values , N ) ;
	royfloyd ( g , values , N ) ;

	free_matrix ( values , N ) ;
	f.close () ;
	g.close () ;
	return 0 ;

}

void royfloyd ( std :: ostream & g , int ** values , int N ) {

	int  ** final_matrix = new int * [N] ;
	
	for ( int i = 0 ; i < N ; i ++ ) {
	
		final_matrix[i] = new int [N] ;
	
	}
	
	for ( int i = 0 ; i < N ; i ++ ) {
	
		for ( int j = 0 ; j < N ; j ++ ) {
		
			if ( i == j ) { 
			
				final_matrix[i][j] = 0 ;
			
			} else if ( values[i][j] == 0 ) {
				
				final_matrix[i][j] = INF ;
			
			} else {
			
				final_matrix[i][j] = values[i][j] ;
			
			}
		
		}
	
	}
	
	for ( int k = 1 ; k < N ; k ++ ) {
	
		for ( int i = 0 ; i < N ; i ++ ) {
		
			for ( int j = 0 ; j < N ; j ++ ) {
			
				if ( final_matrix[i][j] > final_matrix[i][k] + final_matrix[k][j] ) {
				
					final_matrix[i][j] = final_matrix[i][k] + final_matrix[k][j] ;
				
				}
			
			}
		
		}
	
	}
	
	print_matrix ( g , final_matrix , N ) ;
	
	free_matrix ( final_matrix , N ) ;

}


void free_matrix ( int ** matrix , int N ) {

	for ( int i = 0 ; i < N ; i ++ ) {
	
		delete [] matrix[i] ;
	
	}
	
	delete [] matrix ;

}

void read_data ( std :: istream & f , int & N ) {

	f >> N ;

}


void read_matrix ( std :: istream & f , int ** matrix , int N ) {

	for ( int i = 0 ; i < N ; i ++ ) {
	
		for ( int j = 0 ; j < N ; j ++ ) {
		
			f >> matrix[i][j] ;
		
		}
	
	}

}


void print_matrix ( std :: ostream & g , int ** matrix , int N ) {

	for ( int i = 0 ; i < N ; i ++ ) {
	
		for ( int j = 0 ; j < N ; j ++ ) {
		
			if ( matrix[i][j] == INF ) {
			
				g << "0 " ;
			
			} else {
		
				g << matrix[i][j] << ' ' ;
	
			}
			
		}
		
		g << '\n' ;
	
	}

}