#include <iostream>
#include <fstream>

using namespace std;

typedef unsigned long ulong;

int main(int argc, char * argv[]) 
{
	
	const char * inFile = "royfloyd.in";
	const char * outFile = "royfloyd.out";
	
	ifstream fin(inFile);
	ofstream fout(outFile);
	
	#ifndef NDEBUG
		if(!fin || !fout)
		{
			cerr << "Error opening one of \"" << inFile << "\" or \"" << outFile << "\"" << endl;
			return -1;
		}
	#endif
	
	/**
	 *	Read the data in.
	 */
	ulong numVertices;
	fin >> numVertices;
	
	ulong costMatrix[numVertices + 1][numVertices + 1];
		
	for(ulong i = 1; i <= numVertices; i++)
	{
		for(ulong j = 1; j <= numVertices; j++)
		{
			fin >> costMatrix[i][j];
		}
	}
	
	/**
	 *	Solve the problem.
	 */
	for(ulong k = 1; k <= numVertices; k++)
	{
		for(ulong i = 1; i <= numVertices; i++)
		{
			for(ulong j = 1; j <= numVertices; j++)
			{
				/**
				 *	We're only interested in paths that go from one location to a 
				 *	different location and not in paths that go from X to back to X.
				 */
				if(i != j)
				{
					/**
					 *	If there's a way to get from I to K and from K to J...
					 */
					if(costMatrix[i][k] != 0 && costMatrix[k][j] != 0)
					{
						/**
						 *	Then compute its cost and see if its smaller than the previous cost.
						 */
						ulong through_k = costMatrix[i][k] + costMatrix[k][j];
						
						if(through_k < costMatrix[i][j] || costMatrix[i][j] == 0)
							costMatrix[i][j] = through_k;
					}
				}
			}
		}
	}
	
	for(ulong i = 1; i <= numVertices; i++)
	{
		for(ulong j = 1; j <= numVertices; j++)
		{
			fout << costMatrix[i][j] << " ";
		}
		
		fout << "\n";
	}
	
	/**
	 *	Cleanup!
	 */
	fout.close();
	fin.close();
	
	return 0;
}