bolt
Try our new interface for solving problems
Problems

# 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}
Time limit 1 second
Memory limit 128 MiB
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