#include <stdio.h>

unsigned short ** readMatrix (FILE *in, int *n) {
	fscanf(in, "%d", n);
	
	unsigned short **m = new unsigned short *[*n];
	for (int i = 0; i < *n; ++i) {
		m[i] = new unsigned short [*n];
		for (int j = 0; j < *n; ++j) {
			fscanf(in, "%hu", &m[i][j]);
		}
	}
	
	return m;
}

void royfloyd (unsigned short **m, int n) {
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (m[i][k] && m[k][j]) {
					unsigned short s = m[i][k] + m[k][j];
					if (s < m[i][j]) m[i][j] = s;
				}
			}
		}
	}
}

int main (void) {
	FILE *in = fopen("royfloyd.in", "r");
	
	int n;
	unsigned short **m = readMatrix(in, &n);
	fclose(in);
	
	royfloyd(m, n);
	
	FILE *out = fopen("royfloyd.out", "w");
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			fprintf(out, "%d ", m[i][j]);
		}
		fprintf(out, "\n");
	}
	
	for (int i = 0; i < n; ++i) {
		delete[] m[i];
	}
	delete[] m;
	
	
	return 0;
}