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

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

Вхідні дані

Перший рядок містить натуральні числа $n$, $m$, $s$ і $f(n\le 5000,m\le 10^5,1\le s,f\le n,s\ne f)$ — кількість вершин та ребер графа а також номери вершин, довжину шляху між якими потрібно знайти.

Наступні $m$ рядків містять по три натуральних числа $b_i$, $e_i$ і $w_i$ — номери кінців $i$-го ребра та його вагу відповідно $(1\le b_i,e_i\le n,0\le w_i\le 10^5)$.

Вихідні дані

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

Приклади