Breadth First Search 0-1

Undirected graph is given. The weights of its edges can be $0$ or $1$ only. Find the shortest distance from source $s$ to destination $d$.

Input

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

Output

Print the shortest distance from $s$ to $d$.

Examples