eolymp
Problems

Distance between the vertices

Distance between the vertices

Time limit 1 second
Memory limit 128 MiB

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

Input data

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

Output data

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.

Examples

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