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

Вхідні дані

Перший рядок містить натуральні числа n, m, s і f (n ≤ 5000, m ≤ 100000, 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.