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

int main() {
	int n, i, j, k, a1, a2, a3;
	int *mpond;
	FILE *fis;
	char *buff, *poz;

	fis = fopen("royfloyd.in", "rt");
	fscanf(fis, "%i", &n);
	mpond = (int*)malloc(sizeof(int)*n*n);
	buff = (char*)malloc(sizeof(char)*4*n);
	fgets(buff, 256, fis);
	for(i = 0; i < n; i++) {
		fgets(buff,4*n,fis);
		poz = strtok(buff," ");
		for(j = 0; j < n; j++) {
			sscanf(poz,"%i ",mpond+i*n+j);
			poz = strtok(NULL," ");
		}
	}
	fclose(fis);

	for(k = 0; k < n; k++) 
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				a1 = *(mpond + i*n+k);
				a2 = *(mpond + k*n+j);
				a3 = *(mpond + i*n+j);
				if((a1 + a2 < a3 || !a3) && i != j && a1 && a2)
					*(mpond+i*n+j) = a1 + a2;
			}


	fis = fopen("royfloyd.out", "wt");
	for(i = 0; i < n; i++) {
		poz = buff;
		for(j = 0; j < n; j++) {
			sprintf(poz,"%i ", *(mpond+i*n+j));
			poz = strrchr(poz, '\0');
		}
		poz = strrchr(poz, '\0');
		*poz = '\n';
		*(poz+1) = '\0';
		fputs(buff, fis);
	}
	fclose(fis);

	free(buff);
	free(mpond);
	return 0;
}