#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int a[101][101], t[101][101];

void drum(int x, int y)
{
	int k = t[x][y];
	if (k == x)printf("%d ", y);
	else
	{
		drum(x, k);
		drum(k, y);
	}
}

int main()
{
	int n, i, j, k;
	FILE *f = fopen("royfloyd.in", "r");
	fscanf(f, "%d", &n);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
		{
			fscanf(f, "%d", &a[i][j]);
			if (a[i][j])t[i][j] = i;
		}
	for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				if (i != j&&i != k&&j != k)
					if (a[i][k] && a[k][j] && (a[i][j] == 0 || a[i][k] + a[k][j]<a[i][j]))
					{
						a[i][j] = a[i][k] + a[k][j];
						t[i][j] = k;
					}
	fclose(f);
	FILE *g = fopen("royfloyd.out", "w");
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			fprintf(g,"%2d ", a[i][j]);
		fprintf(g,"\n");
	}
	return 0;
}