有一個包含 $N$ 個頂點（編號從 $1$ 到 $N$）與 $M$ 條無向加權邊的簡單圖。

使用邊在兩個頂點間移動時，所需時間為該邊的權重。例如，使用權重為 $3$ 的邊在兩個頂點間移動需要 $3$ 小時。在移動過程中，人不會停留在任何頂點上。也可以選擇不使用邊，停留在頂點上等待時間流逝。

你必須從頂點 $1$ 出發，經過頂點 $K$，最後到達頂點 $N$，並儘可能縮短移動時間。

你可以執行最多 $1$ 次以下的回溯行為：

• 移動到 $T$ 小時前所在的頂點。執行此行為前後都必須位於頂點上。若出發時間未滿 $T$ 小時，則無法執行此行為。

請計算在最多使用 $1$ 次回溯行為的情況下，從頂點 $1$ 出發，經過頂點 $K$ 並到達頂點 $N$ 所需的最小時間。

輸入格式

第一行包含簡單圖的頂點數 $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)$

接下來 $M$ 行，每行包含三個以空白分隔的整數 $u$、$v$ 與 $c$，表示連接頂點 $u$ 與 $v$ 的邊，其權重為 $c$。 $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

輸出格式

第一行輸出從頂點 $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