Problems
Breadth First Search 0-1-2
Breadth First Search 0-1-2
Undirected graph is given. The weights of its edges can be 0, 1, or 2 only. Find the shortest distance from source s to destination d.
Input
First line contains four integers: number of vertices n, number of edges m (n, m
≤ 105
), 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 weight w (0 ≤ w ≤ 2).
Output
Print the shortest distance from s to d.
Input example #1
5 5 1 4 1 2 1 2 3 0 3 4 2 1 5 2 4 5 2
Output example #1
3