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

int main() {
	int n, i, j, k;
	int *mpond;
	int *mcost;
	FILE *fis;

	fis = fopen("royfloyd.in", "rt");
	fscanf(fis, "%i", &n);
	mpond = (int*)malloc(sizeof(int)*n*n);
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++)
			fscanf(fis, "%i", mpond + i*n+j);	
			if( *(mpond +i*n+j) == 0)
				*(mpond+i*n+j) = INT_MAX / 2;
	}
	fclose(fis);

	for(k = 0; k < n; k++) 
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(*(mpond+i*n+k) + *(mpond+k*n+j) < *(mpond+i*n+j) && i != k && j != k)
					*(mpond+i*n+j) = *(mpond+i*n+k) + *(mpond+k*n+j);

	fis = fopen("royfloyd.out", "wt");
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++)
			fprintf(fis, "%i ", *(mpond+i*n+j));
		fprintf(fis, "\n");
	}
	fclose(fis);


	free(mpond);
	return 0;
}