#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>

#define INF ((1 << 30) - 1)
typedef std::pair<int, int> edge;

std::vector<int> bellman_ford(std::vector<std::vector<edge> >& graph, int node) {
	int n = graph.size() / 2 - 1;

	std::vector<int> dist(n + 1, INF);
	dist[node] = 0;

	for (int i = 1; i <= n; ++i) {
		for (int u = 0; u <= n; ++u) {
			for (unsigned int j = 0; j < graph[u].size(); ++j) {
				int v = graph[u][j].first;
				int weight = graph[u][j].second;

				if ((dist[u] != INF) && (dist[v] > dist[u] + weight)) {
					dist[v] = dist[u] + weight;
				}
			}
		}
	}

	for (int u = 0; u <= n; ++u) {
		for (unsigned int j = 0; j < graph[u].size(); ++j) {
			int v = graph[u][j].first;
			int weight = graph[u][j].second;

			if ((dist[u] != INF) && (dist[v] > dist[u] + weight)) {
				return std::vector<int>();
			}
		}
	}
	
	return dist;
}

void update_edges(std::vector<std::vector<edge> >& graph, std::vector<int> dist) {
	int n = graph.size() / 2 - 1;
	for (int i = 1; i <= n; ++i) {
		for (unsigned int j = 0; j < graph[i].size(); ++j) {
			graph[i][j].second += dist[i] - dist[j];
		}
	}
}

std::vector<int> dijkstra(std::vector<std::vector<edge> >& graph, int node) {
	int n = graph.size() / 2 - 1;

	std::priority_queue<edge, std::vector<edge>, std::greater<edge> > prio_q;

	std::vector<int> dist(n, INF);

	dist[node - 1] = 0;
	prio_q.push(std::make_pair(0, node));

	while (!prio_q.empty()) {
		int u = prio_q.top().second;
		prio_q.pop();

		if (graph[u].size() != 0) {
			for (unsigned int i = 0; i < graph[u].size(); ++i) {
				int v = graph[u][i].first;
				int weight = graph[u][i].second;
				if (dist[v - 1] > dist[u - 1] + weight) {
					dist[v - 1] = dist[u - 1] + weight;

					prio_q.push(std::make_pair(dist[v - 1], v));
				}
			}
		}
	}
	
	return dist;
}

std::vector<std::vector<int> > shortest_path_all(const std::vector<std::vector<edge> >& graph) {
	int n = graph.size() / 2 - 1;

	std::vector<std::vector<edge> > new_graph = graph;
	for (int i = 1; i <= n; ++i) {
		new_graph[0].push_back(std::make_pair(i, 0));
	}

	std::vector<std::vector<int> > costs;
	std::vector<std::vector<int> > true_costs(n,std::vector<int>(n, INF));

	std::vector<int> dist = bellman_ford(new_graph, 0);

	if (!dist.size()) {
		return std::vector<std::vector<int> >();
	}

	update_edges(new_graph, dist);

	for (int i = 1; i <= n; ++i) {
		costs.push_back(dijkstra(new_graph, i));
	}

	for (unsigned int i = 0; i < costs.size(); ++i) {
		for (unsigned int j = 0; j < costs[i].size(); ++j) {
			true_costs[i][j] = costs[i][j];

			if (true_costs[i][j] == INF) {
				true_costs[i][j] = -1;
			}
		}
	}

	return true_costs;
}

int main() {
    int nNodes, i, j, cost;

    std::ifstream in("royfloyd.in");
    std::ofstream out("royfloyd.out");

    in >> nNodes;

	std::vector<std::vector<edge> > graph(nNodes + 1);

	for (int i = 0; i <= nNodes; ++i) {
		graph.push_back(std::vector<edge>());
	}

    for (i = 1; i <= nNodes; ++i) {
        for (j = 1; j <= nNodes; ++j) {
            in >> cost;

            if (cost) {
                graph[i].push_back(std::make_pair(j, cost));
            }
        }
    }

	std::vector<std::vector<int> > costs = shortest_path_all(graph);

    for (i = 0; i < nNodes; ++i) {
        for (j = 0; j < nNodes; ++j) {
            if (costs[i][j] == INF) {
                costs[i][j] = 0;
            }

            out << costs[i][j] << " ";
        }

        out << "\n";
    }

    return 0;
}