#include <stdio.h>
#include <stdlib.h>

int** read(FILE *f, int *N)
{
	int **a, i, j;
	fscanf(f, "%d", N);

	a = malloc(*N * sizeof(int*));
	for (i = 0; i < *N; i++)
		a[i] = malloc(*N * sizeof(int));

	for (i = 0; i < *N; i++)
		for (j = 0; j < *N; j++)
			fscanf(f, "%d", &a[i][j]);
	return a;
}

void discard(int **a, int N)
{
	int i;
	for (i = 0; i < N; i++)
		free(a[i]);
	
	free(a);
}

void roy_floyd(int **a, int N)
{
	int i, j, k, d;

	for (k = 0; k < N; k++)
		for (i = 0; i < N; i++)
			for (j = 0; j < N; j++) {
				if (i == j || !a[i][k] || !a[k][j])
					continue;

				d = a[i][k] + a[k][j];
				if (d < a[i][j] || !a[i][j])
					a[i][j] = d;
			}
}

void print(FILE *g, int **a, int N)
{
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++)
			fprintf(g, "%d ", a[i][j]);
		fprintf(g, "\n");
	}
}


int main(void)
{
	FILE *f, *g;
	int N, **a = NULL;

	f = fopen("royfloyd.in", "rt");
	g = fopen("royfloyd.out", "wt");

	a = read(f, &N);
	roy_floyd(a, N);
	print(g, a, N);

	discard(a, N);
	fclose(f);
	fclose(g);
	return 0;
}