#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

typedef vector<vector<int>> graph;
const int INF = int(1e9);

void print(graph g)
{
    for (int i = 0; i < int(g.size()); ++i)
    {
        cout << i + 1 << ": ";
        for (int j = 0; j < int(g[i].size()) - 1; ++j)
            cout << g[i][j] + 1 << ", ";

        if (g[i].size() > 0)
            cout << g[i].back() + 1;
        else
            cout << "нет смежных вершин";

        cout << ";" << endl;
    }
}

void print2D(graph g)
{
    int n = int(g.size());
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n - 1; ++j)
            cout << setw(5) << g[i][j] << ",";
        cout << setw(5) << g[i][n - 1] << endl;
    }
}

// Написание данного алгоритма сильно упрощается, если использовать
// матрицу смежности, а не список смежности.
void init(graph *g, int n, int k)
{
    for (int i = 0; i < n; ++i)
    {
        auto v = new vector<int>(n, k);
        (*g)[i] = *v;
    }
}

// В данной функции вычисляются массивы предков для каждой из вершин.
// В результате получается матрица по которой можно восстановить
// кратчайший путь между любой парой вершин без дополнительных вычислений.
graph dijkstra(graph g, int n)
{
    graph d(n), u(n), p(n);
    init(&d, n, INF);
    init(&u, n, 0);
    init(&p, n, -1);

    // s - начальная вершина
    for (int s = 0; s < n; ++s)
    {
        d[s][s] = 0;
        for (int _ = 0; _ < n; ++_)
        {
            int m = INF;
            int v = -1;
            for (int p = 0; p < n; ++p)
            {
                if (u[s][p] == 1 || d[s][p] == -1) continue;
                if (d[s][p] < m)
                {
                    m = d[s][p];
                    v = p;
                }
            }
            u[s][v] = 1;

            // Производим релаксации
            for (int to = 0; to < n; ++to)
            {
                int len = g[v][to];
                // Релаксации производтяся только в соседние для v вершины.
                if (len == -1) continue;

                int new_len = d[s][v] + len;
                if (new_len < d[s][to])
                {
                    d[s][to] = new_len;
                    p[s][to] = v;
                }
            }
        }
    }
    return p;
}

vector<int> backtrack(graph paths, int start, int end)
{
    vector<int> path;
    int cur = end;
    while (cur != start)
    {
        path.push_back(cur);
        cur = paths[start][cur];
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

int main()
{
    cout << "Введите количество вершин: ";
    int n;
    cin >> n;

    cout << "Введите количество рёбер: ";
    int k;
    cin >> k;

    graph g(n);
    init(&g, n, -1);

    cout << "o----------------------o" << endl;
    cout << "| Нумерация вершин с 1 |" << endl;
    cout << "o----------------------o" << endl;

    cout << "Введите рёбра (неориентированные, взвешенные):" << endl;
    for (int i = 0; i < k; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        g[a][b] = c;
        g[b][a] = c;

        g[a][a] = 0;
        g[b][b] = 0;
    }

    cout << "Введённый граф:" << endl;
    print2D(g);

    graph paths = dijkstra(g, n);

    cout << "Введите начальную вершину: ";
    int a;
    cin >> a;
    a--;

    cout << "Введите конечную вершину: ";
    int b;
    cin >> b;
    b--;

    auto path = backtrack(paths, a, b);
    if (path.size() > 0)
    {
        for (int i = 0; i < int(path.size()) - 1; ++i)
            cout << path[i] + 1 << " -> ";
        cout << path.back() + 1 << endl;
    }
    else
        cout << "Путь не найден" << endl;

    return 0;
}