e-olymp
Задачи

Расстояние между вершинами

Расстояние между вершинами

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

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

Первая строка входного файла содержит натуральные числа N, M, S и F (N5000, M100000, 1S, FN, SF) - количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие M строк содержат по три натуральных числа bi, ei и wi - номера концов i-ого ребра и его вес соответственно (1bi, eiN, 0wi100000).

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные
4 4 1 3
1 2 1
3 4 5
3 2 2
4 1 4
Выходные данные
3
1 2 3