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.

## 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