e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dijkstra algorithm

Distance between the vertices

Undirected weighted graph is given. Find the weight of the minimal path between two vertices.

Input

First line contains positive integers n, m, s and f (n5000, m105, 1s, fn, sf) - 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 bi, ei и wi - the ends of the i-th edge and its weight (1bi, ein, 0wi105).

Output

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.

prb625.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