#include <iostream>
#include <fstream>
#include <unordered_map>
#include <list>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f("royfloyd.in");
ofstream o("royfloyd.out");

class Graf {
	int noduri, muchii;
	unordered_map<int, list<int>>vecini;
	unordered_map<int, bool> vizitat;
	stack<int>stiva_sortare_topologica;
	unordered_map<int, list<int>>vecini_transp;
	unordered_map<int, int>vizitat_transp;
	stack<int>timp_vizitare;
	unordered_map<int, list<int>>componente_tare_conexe;

public:
	Graf(int n);
	Graf(int n, int m);
	int get_noduri();
	int get_muchii();
	int get_vizitat(int nod);
	void adauga_muchie_neorientat(int nod1, int nod2);
	void adauga_muchie_orientat(int nod1, int nod2);
	void sorteaza();
	void dfs(int nod);
	void componente_conexe();
	void bfs(int nod);
	void sortare_topologica();
	void tool_sortare_topologica(int nod);
	void dfs_graf_transpus(int nod, int rezultat);
	void tare_conexitate();
	void apm();
	void initializare(vector<int>& tata, vector<int>& h, int nod);
	int reprezentant(vector<int>& tata, int nod);
	void reuneste(vector<int>& tata, vector<int>& h, int nod1, int nod2);
	void disjoint(int nr_operatii);
	void diametrul_unui_arbore();
	int reprezentant_diametru_arbore(vector<int>& reprezentant, int fiu, int tata, int radacina);
	void roy_floyd();
};

Graf::Graf(int n)
{
	this->noduri = n;
	this->muchii = 0;
	for (int i = 1; i <= n; i++)
		vizitat[i] = vizitat_transp[i] = 0;
}

Graf::Graf(int n, int m)
{
	this->noduri = n;
	this->muchii = m;
	for (int i = 1; i <= n; i++)
		vizitat[i] = vizitat_transp[i] = 0;
}

int Graf::get_noduri()
{
	return this->noduri;
}

int Graf::get_muchii()
{
	return this->muchii;
}

int Graf::get_vizitat(int nod)
{
	return vizitat[nod];
}

void Graf::adauga_muchie_neorientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini[nod2].push_back(nod1);
}

void Graf::adauga_muchie_orientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini_transp[nod2].push_back(nod1);
}

void Graf::sorteaza()
{
	for (int i = 1; i <= noduri; i++)
		vecini[i].sort();
}

void Graf::dfs(int nod)
{
	//cout << nod << " ";
	vizitat[nod] = 1;

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			dfs(*i);

	timp_vizitare.push(nod);
}

void Graf::dfs_graf_transpus(int nod, int rezultat)
{
	componente_tare_conexe[rezultat].push_back(nod);

	vizitat_transp[nod] = 1;

	for (auto i = vecini_transp[nod].begin(); i != vecini_transp[nod].end(); i++)
		if (vizitat_transp[*i] != 1)
			dfs_graf_transpus(*i, rezultat);
}

void Graf::componente_conexe()
{
	int sol = 0;
	sorteaza();

	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
		{
			sol += 1;
			dfs(i);
		}

	o << sol;
}

void Graf::tare_conexitate()
{
	int rezultat = 0;

	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
			dfs(i);

	while (timp_vizitare.size())
	{
		if (vizitat_transp[timp_vizitare.top()] != 1)
		{
			rezultat++;
			dfs_graf_transpus(timp_vizitare.top(), rezultat);
		}
		timp_vizitare.pop();
	}
	o << rezultat;

	for (int i = 1; i <= rezultat; i++)
	{
		o << "\n";
		//componente_tare_conexe[i].sort();
		for (auto j = componente_tare_conexe[i].begin(); j != componente_tare_conexe[i].end(); j++)
			o << *j << " ";
	}
}

void Graf::bfs(int nod)
{
	int start = nod;
	queue<int>coada;
	vizitat[nod] = 1;
	coada.push(nod);
	unordered_map<int, int>distanta;

	for (int i = 1; i <= noduri; i++)
		distanta[i] = 0;

	while (coada.size())
	{
		nod = coada.front();
		//cout << nod << " ";
		coada.pop();
		for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
			if (!vizitat[*i])
			{
				vizitat[*i] = 1;
				coada.push(*i);
				distanta[*i] = distanta[nod] + 1;
			}
	}
	for (int i = 1; i <= noduri; i++)
		if (i != start && distanta[i] == 0)
			o << "-1" << " ";
		else
			o << distanta[i] << " ";
}

void Graf::tool_sortare_topologica(int nod)
{
	vizitat[nod] = 1;

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			tool_sortare_topologica(*i);

	stiva_sortare_topologica.push(nod);
}

void Graf::sortare_topologica()
{
	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
			tool_sortare_topologica(i);

	while (stiva_sortare_topologica.size())
	{
		o << stiva_sortare_topologica.top() << " ";
		stiva_sortare_topologica.pop();
	}
}

void Graf::apm()
{
	struct muchie
	{
		int st, dr, cost;
		bool operator <(const muchie& b)
		{
			return cost < b.cost;
		}
	};

	vector<muchie>v;
	v.resize(muchii);

	for (int i = 0; i < muchii; i++)
		f >> v[i].st >> v[i].dr >> v[i].cost;

	sort(v.begin(), v.end());

	vector<int>tata;
	vector<int>h;

	tata.resize(noduri + 1);
	h.resize(noduri + 1);

	for (int i = 1; i <= noduri; i++)
		initializare(tata, h, i);

	int suma = 0, nr_muchii = 0;

	vector<pair<int, int>>de_afisat;

	for (int i = 0; i < muchii; i++)
	{
		if (reprezentant(tata, v[i].st) != reprezentant(tata, v[i].dr))
		{
			suma += v[i].cost;
			de_afisat.push_back(make_pair(v[i].st, v[i].dr));
			reuneste(tata, h, v[i].st, v[i].dr);
			nr_muchii += 1;
			if (nr_muchii == noduri - 1)
				break;
		}	

	}

	o << suma << "\n";
	o << nr_muchii << "\n";
	for (auto i : de_afisat)
		o << i.first << " " << i.second << " \n";
}

void Graf::initializare(vector<int>& tata, vector<int>& h, int nod)
{
	tata[nod] = h[nod] = 0;
}

int Graf::reprezentant(vector<int>& tata, int nod)
{
	while (tata[nod] != 0)
		nod = tata[nod];
	
	return nod;
}

void Graf::reuneste(vector<int>& tata, vector<int>& h, int nod1, int nod2)
{
	int repr_nod1 = reprezentant(tata, nod1);
	int repr_nod2 = reprezentant(tata, nod2);

	if (h[repr_nod1] > h[repr_nod2])
		tata[repr_nod2] = repr_nod1;
	else 
	{
		tata[repr_nod1] = repr_nod2;
		
		if (h[repr_nod1] == h[repr_nod2])
			h[repr_nod2] ++;
	}
}

void Graf::disjoint(int nr_operatii)
{
	vector<int>tata;
	vector<int>h;

	tata.resize(noduri + 1);
	h.resize(noduri + 1);

	for (int i = 1; i <= noduri; i++)
		initializare(tata, h, i);

	for (int i = 0; i < nr_operatii; i++)
	{
		int cod, x, y;

		f >> cod >> x >> y;

		if (cod == 1)
		{
				reuneste(tata, h, x, y);
		}
		else
		{
			if (reprezentant(tata, x) == reprezentant(tata, y))
				o << "DA" << "\n";
			else
				o << "NU" << "\n";
		}
	}
}

void Graf::diametrul_unui_arbore()
{
	int tata, fiu, radacina;

	vector<int>reprezentant;
	reprezentant.resize(noduri + 1);

	vector<int>distante;
	distante.resize(noduri + 1);

	for (int i = 0; i <= noduri; i++)
		reprezentant[i] = distante[i] = 0;

	f >> radacina >> fiu;
	reprezentant[fiu] = radacina;

	distante[radacina] = 1;
	distante[fiu] = distante[radacina] + 1;

	for (int i = 1; i < noduri; i++)
	{
		f >> tata >> fiu;

		if (tata == radacina)
		{
			reprezentant[fiu] = radacina;
			distante[fiu] = distante[radacina] + 1;
		}

		else
		{
			reprezentant[fiu] = reprezentant_diametru_arbore(reprezentant, fiu, tata, radacina);
			distante[fiu] = distante[tata] + 1;
		}
	}

	sort(distante.begin(), distante.end());

	int ok = 1;

	for (int i = noduri; i >= 2; i--)
	{
		for(int j = i - 1; j >= 1; j--)
			if (reprezentant[i] != reprezentant[j])
			{
				o << distante[i] + distante[j] - 1;
				ok = 0;
				break;
			}
		if (ok == 0)
			break;
	}
}

int Graf::reprezentant_diametru_arbore(vector<int>& reprezentant, int fiu, int tata, int radacina)
{
	while (tata != radacina)
	{
		fiu = tata;
		tata = reprezentant[tata];
	}

	return fiu;
}

void Graf::roy_floyd()
{
	int inf = 1000000;

	vector<vector<int>>distante;
	vector<vector<int>>predecesori;

	distante.resize(noduri + 1);
	predecesori.resize(noduri + 1);

	for (int i = 1; i <= noduri; i++)
	{
		distante[i].resize(noduri + 1);
		predecesori[i].resize(noduri + 1);
	}

	for (int i = 1; i <= noduri; i++)
		for (int j = 1; j <= noduri; j++)
		{
			f >> distante[i][j];

			if (i != j && distante[i][j] == 0)
			{
				distante[i][j] = inf;
				predecesori[i][j] = 0;
			}

			else
				predecesori[i][j] = i;
		}

	for (int k = 1; k <= noduri; k++)
		for (int i = 1; i <= noduri; i++)
			for (int j = 1; j <= noduri; j++)
				if (distante[i][j] > distante[i][k] + distante[k][j])
				{
					distante[i][j] = distante[i][k] + distante[k][j];
					predecesori[i][j] = predecesori[k][j];
				}
	for (int i = 1; i <= noduri; i++)
	for (int j = 1; j <= noduri; j++)
		if (distante[i][j] == inf || i == j)
			distante[i][j] = 0;

	for (int i = 1; i <= noduri; i++)
	{
		for (int j = 1; j <= noduri; j++)
			o << distante[i][j] << " ";
		o << "\n";
	}
}

int main()
{
	int N;

	f >> N;

	Graf g(N);

	g.roy_floyd();

	return 0;
}