#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] = 100000;

		}

	for (int i = 0; i < number_of_vertices; i++)
		for (int j = 0; j < number_of_vertices; j++)
			for (int k = 0; k < number_of_vertices; k++)
				if (adjacency_matrix[i][k] > adjacency_matrix[i][j] + adjacency_matrix[j][k])
					adjacency_matrix[i][k] = adjacency_matrix[i][j] + adjacency_matrix[j][k];
			
	for (int i = 0; i < number_of_vertices; i++)
	{
		for (int j = 0; j < number_of_vertices; j++)
			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;
}