/*
 * e_003_floyd_warshall.cpp
 *
 *  Created on: May 11, 2015
 *      Author: Marius
 */

#include <fstream>
#include <limits>
#include <iostream>
using namespace std;

//int e_003_royfloyd()
int main()
{
	string in_file = "royfloyd.in";
	string out_file = "royfloyd.out";

	int N;
	const int MAX_N = 100;
	int weights[MAX_N + 1][MAX_N + 1];
	//read the inputs
	ifstream ifs(in_file);
	if (!ifs.is_open())
	{
		std::cout << "Input file not found" << std::endl;
		return 1;
	}
	ifs >> N;
	for (int v = 1; v <= N; v++)
		for (int v2 = 1; v2 <= N; v2++)
			ifs >> weights[v][v2];
	ifs.close();

	//processing
	int min_paths[MAX_N + 1][MAX_N + 1];

	for (int u = 1; u <= N; u++)
	{
		for (int v = 1; v <= N; v++)
			if (weights[u][v] != 0)
				min_paths[u][v] = weights[u][v];
			else
				// max/2 in order to avoid a + b overflow
				min_paths[u][v] = std::numeric_limits<int>::max() / 2;

		min_paths[u][u] = 0;
	}

	for (int u = 1; u <= N; u++)
		for (int v = 1; v <= N; v++)
			for (int w = 1; w <= N; w++)
				min_paths[u][v] = min(min_paths[u][v], min_paths[u][w] + min_paths[w][v]);

	ofstream ofs(out_file);
	for (int v1 = 1; v1 <= N; v1++)
	{
		for (int v2 = 1; v2 <= N; v2++)
			ofs << min_paths[v1][v2] << " ";
		ofs << endl;
	}
	ofs.close();

	return 0;
}