Competitions

# Breadth First Search

# 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**
≤ `10`

), source ^{5}**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 weight **w** (**0** ≤ **w** ≤ **1**).

#### Output

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

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