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≤ 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).

Output

Print the shortest distance from s to d.

Examples