An undirected weighted graph is given. Find the weight of the minimal path between two vertices.
The first line contains positive integers n, m, s and f(n≤5000,m≤105,1≤s,f≤n,s=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 bi, ei and wi — the ends of the i-th edge and its weight (1≤bi,ei≤n,0≤wi≤105).
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.