# Breadth First Search 0-1

Very easy

Execution time limit is 3 seconds

Runtime memory usage limit is 128 megabytes

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≤10_{5})$, source $s$ and destination $d(1≤s,d≤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≤w≤1)$.

## Output

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

## Examples

Input #1

Answer #1

Submissions 2K

Acceptance rate 48%