Задачі
Відстань між вершинами
Відстань між вершинами
Задано неорієнтовний зважений граф. Знайти вагу мінімального шляху між двома вершинами.
\InputFile
Перший рядок містить натуральні числа $n$, $m$, $s$ і $f\:(n \le 5000, m \le 10^5, 1 \le s, f \le n, s \neq f)$ --- кількість вершин та ребер графа а також номери вершин, довжину шляху між якими потрібно знайти.
Наступні $m$ рядків містять по три натуральних числа $b_i$, $e_i$ і $w_i$ --- номери кінців $i$-го ребра та його вагу відповідно $(1 \le b_i, e_i \le n, 0 \le w_i \le 10^5)$.
\OutputFile
У першому рядку вивести вагу мінімального шляху між вершинами $s$ та $f$. У другому рядку через пропуск виведіть вершини на найкоротшому шдяху з $s$ у $f$ у порядку обходу. Якщо шлях з $s$ у $f$ не існує, виведіть $-1$.
\includegraphics{https://static.e-olymp.com/content/45/4553e1879d5b2920b67d19be8688d1057e1ce444.gif}
Вхідні дані #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Вихідні дані #1
3 1 2 3