#include <iostream>
#include <fstream>
#include <string>
#include <iostream>
#include <cstring>
#include <cstdlib>

// nasza stala okresla nieskonczonosc
static const int nieskonczonosc = 10000;
int main()
{
	int A[100][100];
	int D[100];
	int N, n;

	std::fstream plik;
	plik.open("graf.txt", std::ios::in | std::ios::out);

	if (!plik.good())
		std::cout << "Brak pliku graf.txt!" << std::endl;
	else
	{
		plik >> n;
		std::cout << "Liczba wierzcholkow: " << n << std::endl << std::endl;

		std::string liczba;
		//std::cout << "Zawartosc pliku: " << std::endl;
		//std::cout << "================" << std::endl;
		for (int j = 0; j < n; j++)
		{
			for (int i = 0; i < n; i++)
			{

				plik >> liczba;
				if (liczba == "*")
					A[i][j] = nieskonczonosc;
				else
				{
					int temp = atoi(liczba.c_str());
					A[i][j] = temp;
				}
				//std::cout << A[i][j] << ", ";
			}
			//std::cout << std::endl;
		}
		std::cout << "================" << std::endl;
		plik.close();

		//std::cout << "Poczatkowa zawartosc D[i]: " << std::endl;
		for (int i = 0; i < n; i++)
		{
			D[i] = A[i][0];
			//std::cout << D[i] << ", ";
		}
		//std::cout << std::endl << std::endl;

		for (int k = 1; k <= n - 2; k++)
		{
			for (int i = 1; i < n; i++)
			{
				for (int j = 0; j<n; j++)
				{
					if (D[j] + A[i][j]>nieskonczonosc)
						N = nieskonczonosc;
					else
						N = D[j] + A[i][j];
					D[i] = (D[i] < N) ? D[i] : N;
				}
			}
		}
		std::cout << std::endl;

		for (int i = 0; i < n; i++)
		{
			if (D[i] < nieskonczonosc)
				std::cout << "D[" << i + 1 << "]" << "= " << D[i] << std::endl;
			else
				std::cout << "D[" << i + 1 << "]" << "= " << "*" << std::endl;
		}
	}

	return EXIT_SUCCESS;
}