#include <fstream>
using namespace std;

int main(int argc, char **argv)
{
	ifstream indata("royfloyd.in");
	
	// input data
	int n;
	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];
		}
	}
	
	// apply Roy-Floyd to find shortestPath
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// 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 data
	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";
	}
	
	indata.close();
	outdata.close();
	return 0;
}