e-olymp
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, m105), source s and destination d (1s, dn). Each of the next m lines contains three integers a, b and w describing an undirected edge (a, b) with weight w (0w1).

Output

Print the shortest distance from s to d.

prb10056.gif

Time limit 3 seconds
Memory limit 128 MiB
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
Author Mykhailo Medvediev