#include <iostream>
#include <fstream>
#include <vector>

const int infinity = INT_MAX;  //обозначение несуществующего пути из одной вершины в другую


class Graph {
    size_t size;  //размер графа (кол-во вершин)
    int **matrix;  //матрица смежности

public:
    //конструктор графа (надо переделать со вводом из файла)
    Graph(std::istream &in) {
        in >> size;

        matrix = new int*[size];
        for (size_t i = 0; i < size; ++i)
            matrix[i] = new int[size];

        for (size_t i = 0; i < size; ++i) {
            for (size_t j = 0; j < size; ++j) {
                in >> matrix[i][j];
            }
        }
    }

    //вывод матрицы на экран
    void show() {
        for (size_t i = 0; i < size; ++i) {
            for (size_t j = 0; j < size; ++j) {
                std::cout << matrix[i][j]<< " ";
            }
            std::cout << std::endl;
        }
    }

    //дальше методы нашего алгоритма
    void alg_floyd() {
        int x;
        for (size_t k = 0; k < size; ++k) {
            for (size_t i = 0; i < size; ++i) {
                for (size_t j = 0; j < size; ++j) {
                    if ((k == i) || (k == j) || (i == j)
                        || (matrix[i][k] == infinity) || (matrix[k][j] == infinity)) continue;
                    if (matrix[i][j] >= (matrix[i][k] + matrix[k][j])) {
                        x = (matrix[i][k] + matrix[k][j]);
                        matrix[i][j] = x;
                    }
                }
            }
        }
    }

    void short_path(int x, int y) {
        std::cout << x;
        std::cout << " - " << matrix[x][y] << " - ";
        std::cout << y;
    }



};

int main()
{
    std::ifstream in("input.txt");
    Graph object(std::cin);
    object.show();
    std::cout << "\n\n";
    object.alg_floyd();
    object.show();
    std::cout << "Enter vershini: \n";
    char x, y;
    std:: cin >> x >> y;
    object.short_path(x, y);

    system("pause");
    return 0;
}