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.
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 weight w (0 ≤ w ≤ 2).
Print the shortest distance from s to d.