Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.
Первая строка содержит натуральные числа n и m (n ≤ 2000, m ≤ 50000) - количество вершин и рёбер графа. Вторая строка содержит натуральные числа s и f (1 ≤ s, f ≤ n, s ≠ f) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат по три числа b[i]
, e[i]
и w[i]
- номера концов i-ого ребра и его вес соответственно (1 ≤ b[i]
, e[i]
≤ n, 0 ≤ w[i]
≤ 100000).
Первая строка должна содержать одно число - длину минимального пути между вершинами s и f. Во второй строке через пробел выведите вершины на кратчайшем пути из s в f в порядке обхода. Если путь из s в f не существует, выведите -1.