Problem Statement

$N$ buildings are lined up in order from Building $1$ to Building $N$.
Every building has $K$ floors, and one can move between floors $1$ through $K$ using stairs.

Furthermore, there are $M$ connecting corridors between these buildings,
and the $i$-th corridor allows movement only in the direction from floor $b_i$ of Building $a_i$ to floor $c_i$ of Building $a_i+1$.

T-kun wants to move from floor $S$ of Building $1$ to floor $T$ of Building $N$, using the stairs as little as possible.
Find the minimum number of floors he needs to go up or down by stairs.

However, since T-kun does not want to go outside, he uses only the corridors to move between buildings.
If he cannot reach the destination, output $-1$.

Input

$N$ $M$ $K$ $S$ $T$
$a_1$ $b_1$ $c_1$
$:$
$a_M$ $b_M$ $c_M$

The first line contains $N$, $M$, $K$, $S$, $T$.
The following $M$ lines, starting from the second line, contain the corridor information $a_i$, $b_i$, $c_i$.
All inputs are integers and satisfy the following constraints.
$1 \leqq N \leqq 2 \times 10^5$
$0 \leqq M \leqq 2 \times 10^5$
$1 \leqq K \leqq 10^9$
$1 \leqq S, T \leqq K$
$1 \leqq a_i \leqq N - 1$ ($1 \leqq i \leqq M$)
$1 \leqq b_i, c_i \leqq K$ ($1 \leqq i \leqq M$)
$(a_i, b_i, c_i) \neq (a_j, b_j, c_j) (i \neq j)$

Output

Output the minimum number of floors T-kun needs to go up or down by stairs, followed by a newline.

Sample

2 1 5 1 5
1 3 4

3

2 2 10 10 1
1 9 5 
1 6 1

4

2 0 5 1 5

-1