#include <fstream>

using namespace std;

struct Graf_RMP{
	short n;
	short **a;
};

void citeste(const char filename[], Graf_RMP &graf){
	ifstream fin(filename);
	fin >> graf.n;
	graf.a = new short int* [graf.n + 1];
	for(int i = 1; i <= graf.n; ++i){
		graf.a[i] = new short int [graf.n + 1];
		for(int j = 1; j <= graf.n; ++j){
			fin >> graf.a[i][j];
		}
	}
	
	fin.close();
}

void creeazaMatriceaDrumurilor(const Graf_RMP &graf, int **&matricea_distantelor, int &matricea_distantelor_size){
	matricea_distantelor_size = graf.n;
	matricea_distantelor = new int* [matricea_distantelor_size + 1];
	for(int i = 1; i <= matricea_distantelor_size; ++i){
		matricea_distantelor[i] = new int [matricea_distantelor_size + 1];
		for(int j = 1; j <= matricea_distantelor_size; ++j){
			matricea_distantelor[i][j] = graf.a[i][j];
		}
	}
	
	int dist_temp;
	for(int k = 1; k <= graf.n; ++k){
		for(int i = 1; i <= graf.n; ++i){
		
			for(int j = 1; j < i; ++j){
				if(matricea_distantelor[i][k] != 0 && matricea_distantelor[k][j] != 0){
					dist_temp = matricea_distantelor[i][k] + matricea_distantelor[k][j];
					if(matricea_distantelor[i][j] > dist_temp || matricea_distantelor[i][j] == 0){
						matricea_distantelor[i][j] = dist_temp;
					}
				}
			}
			
			for(int j = i+1; j <= graf.n; ++j){
				if(matricea_distantelor[i][k] != 0 && matricea_distantelor[k][j] != 0){
					dist_temp = matricea_distantelor[i][k] + matricea_distantelor[k][j];
					if(matricea_distantelor[i][j] > dist_temp || matricea_distantelor[i][j] == 0){
						matricea_distantelor[i][j] = dist_temp;
					}
				}
			}
		}
	}
}

void afiseaza(const char filename[], int **matricea_distantelor, int matricea_distantelor_size){
	ofstream fout(filename);
	for(int i = 1; i <= matricea_distantelor_size; ++i){
		for(int j = 1; j < matricea_distantelor_size; ++j){
			fout << matricea_distantelor[i][j] << " ";
		}
		fout << matricea_distantelor[i][matricea_distantelor_size] << "\n";
	}
	
	fout.close();
}

int main(){
	Graf_RMP graf;
	citeste("royfloyd.in", graf);
	
	int **matricea_distantelor;
	int matricea_distantelor_size;
	creeazaMatriceaDrumurilor(graf, matricea_distantelor, matricea_distantelor_size);
	
	afiseaza("royfloyd.out", matricea_distantelor, matricea_distantelor_size);
	return 0;
}