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

Вхідні умови

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

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

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