問題文

$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)\ne (a_j,b_j,c_j)(i\ne 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