$1$番から $N$番まで番号が付けられた $N$個の頂点と $M$個の無向重み付き辺からなる単純グラフがある。

辺を利用して2つの頂点間を移動する際には、その辺の重み分の時間がかかる。例えば、重みが $3$ の辺を利用して2つの頂点間を移動する場合、 $3$ 時間かかる。移動中はどの頂点にも存在しない状態となる。辺を利用せず、頂点にとどまって時間を過ごすこともできる。

あなたは $1$番の頂点から出発し、$K$番の頂点を経由して $N$番の頂点までできるだけ早く移動しなければならない。

あなたは以下の「回帰行動」を最大 $1$回まで行うことができる。

• $T$時間前にいた頂点へ移動する。移動前と移動後の両方で、頂点の上にいなければならない。出発してから $T$時間が経過していない場合は、この行動を行うことはできない。

回帰行動を最大 $1$回使用できるとき、$1$番の頂点から出発して $K$番の頂点を経由し、$N$番の頂点まで移動するのにかかる最小時間を求めよ。

入力

1行目に単純グラフの頂点数 $N$、辺の数 $M$、経由すべき頂点番号 $K$、および $T$ が空白区切りで与えられる。 $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

2行目から $M$行にわたり、各辺が接続する2つの頂点番号 $u, v$ と重み $c$ が空白区切りで与えられる。 $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

出力

1行目に $1$番の頂点から出発して $K$番の頂点を経由し、$N$番の頂点まで移動するのにかかる最小時間を出力せよ。 ただし、そのような移動が不可能な場合は -1 を出力せよ。

入出力例

入力 1

4 3 3 1
1 2 2
2 3 1
2 4 3

出力 1

6

入力 2

4 3 2 0
1 2 1
2 3 2
3 1 3

出力 2

-1