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