#include <fstream>
using namespace std;

///// DESCRIPTION
// THIS PROGRAM FINDS THE MINIMUM
// PATH BETWEEN ALL NODES IN A WEIGHTED
// UNDIRECTED GRAPH IN O(|V|^3) BY
// APPLYING THE FOLLOWING STEP-BY-STEP APPROXIMATIONS:
// https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
// shortestPath(i, j, k) -- returns shortest path between i and j by
//								going through nodes [1...k]
//
// shortestPath(i, j, 0) -- weight(i, j)
// shortestPath(i, j, k+1) -- min(shortestPath(i, j, k), 
//									  shortestPath(i, k+1, k) + shortestPath(k+1, j, k))
/////

int main(int argc, char **argv)
{
	// INPUT
	int n;
	
	ifstream indata("royfloyd.in");
	indata >> n;
	
	int cost_mat[n][n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
				indata >> cost_mat[i][j];
		}
	}
	indata.close();
	
	// APPLY ROY-FLOYD TO FIND SHORTEST_PATH
	for (int k = 0; k < n; k++) { // loop through all possible intermediate nodes
		for (int i = 0; i < n; i++) { // loop through all start nodes
			for (int j = 0; j < n; j++) { // loop through all end nodes
				// if there is a path between [i][k] and [k][j]
				if (cost_mat[i][k] != 0 && cost_mat[k][j] != 0) {
					// if we are not trying to go back and either 1) there was no path before or 2) the new path is shorter
					if((cost_mat[i][j] > cost_mat[i][k] + cost_mat[k][j] || cost_mat[i][j] == 0) && i != j) {
						cost_mat[i][j] = cost_mat[i][k] + cost_mat[k][j];
					}
				}
			}
		}
	}
	
	// OUTPUT
	ofstream outdata("royfloyd.out");
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			outdata << cost_mat[i][j] << " ";
		}
		outdata << "\n";
	}
	
	outdata.close();
	return 0;
}