Distance between the vertices

Input

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 the vertices between which the minimum path weight should be found.

Each of the next $m$ lines contains three integers b_i, e_i and w_i — the endpoints of the $i$-th edge and its weight (1 \le b_i, e_i \le n, 0 \le w_i \le 10^5).

Output

Print the minimum weight of the path between vertices $s$ and $f$ on the first line. On the second line, print the sequence of vertices on the shortest path from $s$ to $f$, space separated, in order. If there is no path from $s$ to $f$, print $-1$.

Examples