#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = numeric_limits<int>::max();

// Функция алгоритма Дейкстры
void dijkstra(const vector<vector<int>>& graph, int start, int end, int n) {
    vector<int> dist(n, INF);           // Расстояния до вершин
    vector<int> prev(n, -1);            // Предыдущие вершины для восстановления пути
    vector<bool> visited(n, false);     // Посещённые вершины

    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != -1 && !visited[v]) {
                int newDist = dist[u] + graph[u][v];
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    if (dist[end] == INF) {
        cout << "Путь не существует." << endl;
    } else {
        cout << "Кратчайший путь: ";
        vector<int> path;
        for (int v = end; v != -1; v = prev[v])
            path.push_back(v);

        reverse(path.begin(), path.end());
        for (size_t i = 0; i < path.size(); ++i) {
            cout << path[i]+1;
            if (i != path.size() - 1)
                cout << " -> ";
        }
        cout << endl;
        cout << "Суммарная стоимость: " << dist[end] << endl;
    }
}

int main() {
    setlocale(LC_ALL, "ru");

    int n;
    cout << "Введите количество вершин графа: ";
    cin >> n;

    vector<vector<int>> graph(n, vector<int>(n));

    cout << "Введите матрицу смежности (" << -1 << " — нет ребра, 0 — петля, >0 — вес):" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }

    int start, end;
    cout << "Начальная и конечная вершины (1-" << n << "): ";
    cin >> start >> end;

    if (start < 1 || start >= n+1 || end < 1 || end >= n+1) {
        cout << "Некорректный ввод вершин." << endl;
        return 1;
    }

    dijkstra(graph, start-1, end-1, n);

    return 0;
}