Distance between the vertices

An undirected weighted graph is given. Find the weight of the minimal path between two 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\ne 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

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