Problems
Distance between the vertices
Distance between the vertices
An undirected weighted graph is given. Find the weight of the minimal path between two vertices.
\InputFile
The first line contains positive integers $n$, $m$, $s$ and $f\:(n \le 5000, m \le 10^5, 1 \le s, f \le n, s \neq f)$ --- the number of vertices and edges in the graph and the numbers of vertices between which the length of the minimum path should be found.
Each of the next $m$ lines contains three positive integers $b_i$, $e_i$ and $w_i$ --- the ends of the $i$-th edge and its weight $(1 \le b_i, e_i \le n, 0 \le w_i \le 10^5)$.
\OutputFile
Print in the first line the minimum weight of the path between vertices $s$ and $f$. In the second line print the vertices on the shortest path from $s$ to $f$ in the bypass order, space separated. If the route from $s$ to $f$ does not exist, print $-1$.
\includegraphics{https://static.e-olymp.com/content/45/4553e1879d5b2920b67d19be8688d1057e1ce444.gif}
Input example #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Output example #1
3 1 2 3