eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кратчайший путь

Кратчайший путь

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

Входные данные

Первая строка содержит натуральные числа n и m (n2000, m50000) - количество вершин и рёбер графа. Вторая строка содержит натуральные числа s и f (1s, fn, sf) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат по три числа b[i], e[i] и w[i] - номера концов i-ого ребра и его вес соответственно (1b[i], e[i]n, 0w[i]100000).

Выходные данные

Первая строка должна содержать одно число - длину минимального пути между вершинами s и f. Во второй строке через пробел выведите вершины на кратчайшем пути из s в f в порядке обхода. Если путь из s в f не существует, выведите -1.

prb4856.gif

Пример

Входные данные #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Выходные данные #1
3
1 2 3