eolymp
Задачі

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

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

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

Вхідні дані

Перший рядок містить натуральні числа 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