問題文

$N$ 棟の建物が第 $1$ 棟から第 $N$ 棟まで順に並んでいる。
建物は全て $K$ 階建てであり、$1$ 階から $K$ 階まで階段を使って行き来できる。

さらに、これらの建物の間には $M$ 個の渡り廊下があり、
$i$ 番目の渡り廊下により第 $a_i$ 棟の $b_i$ 階から第 $a_i+1$ 棟の $c_i$ 階の方向にのみ移動できる。

T君は第 $1$ 棟の $S$ 階から 第 $N$ 棟の $T$ 階まで、できるだけ階段を使わないで移動したい。
この時、階段を上り下りする必要がある階数の最小値を求めよ。

ただし、T君は外に出たくないため、建物間の移動には渡り廊下のみを使う。
辿り着くことができない場合は $-1$ を出力せよ。

入力

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

1行目に $N$, $M$, $K$, $S$, $T$ が与えられる。
2行目からの $M$ 行に、渡り廊下の情報 $a_i$, $b_i$, $c_i$ が与えられる。
入力は全て整数で与えられ、以下の制約を満たす。
$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)$

出力

T君が階段を上り下りする必要がある最小の階数を出力し、最後に改行せよ。

サンプル

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