Problems
Breadth First Search 0-1
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$.
\InputFile
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)$.
\OutputFile
Print the shortest distance from $s$ to $d$.
\includegraphics{https://static.e-olymp.com/content/d4/d41a7d95d5084f6f627f76bd21b509b9458b00b1.gif}
Input example #1
5 5 1 3 1 2 0 2 3 1 3 4 0 4 5 1 1 5 1
Output example #1
1