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

int main()
{
	FILE *input = fopen("royfloyd.in", "r");
	FILE *output = fopen("royfloyd.out", "w");

	int n;
	int **matrix;
	
	fscanf(input, "%d", &n);

	matrix = (int**)malloc(n*sizeof(int*));
	for (int i = 0; i < n; i++)
		matrix[i] = (int*)malloc(n*sizeof(int));

	for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
		fscanf(input, "%d", &matrix[i][j]);

	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (i != j && matrix[i][k] != 0 && matrix[k][j] != 0 &&(matrix[i][k] + matrix[k][j] < matrix[i][j] || matrix[i][j] == 0))
					matrix[i][j] = matrix[i][k] + matrix[k][j];
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			fprintf(output, "%d ", matrix[i][j]);
			printf("%d ", matrix[i][j]);
		}
		fprintf(output, "\n");
		printf("\n");
	}

	getchar();
	return 0;
}