Breadth First Search 0-1

An undirected graph is given. The weight of its edges can be $0$ or $1$ only. Find the shortest distance between vertices $s$ and $d$.

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