Задачи
Расстояние между вершинами
Расстояние между вершинами
Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.
\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