#include <fstream>
#include <vector>
#include <climits>
using namespace std;

ifstream cin("royfloyd.in");
ofstream cout("royfloyd.out");

int n;

void roy_floyd_warshall(vector<vector<int>>& dist, vector<vector<int>>& next) {
	for (int k = 1; k < n + 1; k++) {
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					next[i][j] = next[i][k];
				}
			}
		}
	}
}

int main()
{
	cin >> n;
	vector<int> v(n + 1);
	vector<vector<int>> dist(n + 1, v);
	vector<vector<int>> next(n + 1, v);

	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			cin >> dist[i][j];
			if (dist[i][j] == 0 && i != j) { dist[i][j] = INT_MAX; }
			else {
				next[i][j] = j;
			}
		}
	}

	roy_floyd_warshall(dist, next);

	bool ok = true;  //check for negative cycle
	
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < n + 1; j++) {
			if (i == j && dist[i][i] != 0) { ok = false; }
			cout << dist[i][j] << " ";
		}
		cout << endl;
	}

	if (!ok) { cout << "Negative cycle" << endl; }

}