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

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

	int number_of_vertices;

	fscanf(read, "%d", &number_of_vertices);

	int **adjacency_matrix = (int**) calloc(number_of_vertices, sizeof(int*));

	for(int i = 0; i < number_of_vertices; i++)
		adjacency_matrix[i] = (int*) calloc(number_of_vertices, sizeof(int));


	for(int i = 0; i < number_of_vertices; i++)
		for(int j = 0; j < number_of_vertices; j++)
		{
			fscanf(read, "%d", &adjacency_matrix[i][j]);
		
			if (i != j && adjacency_matrix[i][j] == 0)
				adjacency_matrix[i][j] = 1000000;

		}
	for (int k = 0; k < number_of_vertices; k++)
		for (int i = 0; i < number_of_vertices; i++)
			for (int j = 0; j < number_of_vertices; j++)
					if (adjacency_matrix[i][j] > adjacency_matrix[i][k] + adjacency_matrix[k][j])
						adjacency_matrix[i][j] = adjacency_matrix[i][k] + adjacency_matrix[k][j];
			
	for (int i = 0; i < number_of_vertices; i++)
	{
		for (int j = 0; j < number_of_vertices; j++)
		{
			if (adjacency_matrix[i][j] == 100000)
				adjacency_matrix[i][j] = 0;	

			fprintf(write, "%d ", adjacency_matrix[i][j]);
		}

		fprintf(write, "\n");
	}

	for(int i = 0; i < number_of_vertices; i++)
		free(adjacency_matrix[i]);
	free(adjacency_matrix);

	fclose(read);
	fclose(write);	

	return 0;
}