Найкоротший шлях

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

Вхідні умови

Перший рядок містить натуральні числа n та m (n ≤ 2000, m ≤ 50000) - кількість вершин та ребер графа. Другий рядок містить натуральні числа s та f (1 ≤ s, f ≤ n, s ≠ f) - номери вершин, довжину шляху між якими потріно знайти. Наступні m рядків містять по три числа b[i], e[i] та w[i] - номери кінців i-ого ребра та його вагу відповідно (1 ≤ b[i], e[i] ≤ n, 0 ≤ w[i] ≤ 100000).

Вихідні умови

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

Приклади