e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dijkstra algorithm

Відстань між вершинами

Задано неорієнтовний зважений граф. Знайти вагу мінімального шляху між двома вершинами.

Вхідні дані

Перший рядок містить натуральні числа n, m, s і f (n5000, m100000, 1s, fn, sf`) - кількість вершин та ребер графа а також номери вершин, довжину шляху між якими потрібно знайти.

Наступні m рядків містять по три натуральних числа bi, ei і wi - номери кінців i-го ребра та його вагу відповідно (1bi, ein, 0wi100000).

Вихідні дані

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

prb625.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 4 1 3
1 2 1
2 3 2
3 4 5
4 1 4
Вихідні дані #1
3
1 2 3