Breadth First Search 0-1

Input

The first line contains four integers: the number of vertices $n$, the number of edges m~(n, m \le 10^5), and the vertex numbers $s$ and d~(1 \le s, d \le n). Each of the following $m$ lines contains three integers $a$, $b$, and $w$, representing an undirected edge $(a,b)$ with an integer weight w~(0 \le w \le 1).

Output

Print the shortest distance between vertices $s$ and $d$.

Examples