Дан простой неориентированный взвешенный граф, состоящий из $N$ вершин, пронумерованных от $1$ до $N$, и $M$ ребер.

Перемещение между двумя вершинами по ребру занимает время, равное весу этого ребра. Например, перемещение по ребру с весом $3$ занимает $3$ единицы времени. Во время перемещения вы не находитесь ни в какой вершине. Вы также можете оставаться в вершине, не используя ребра, тратя на это время.

Вам необходимо как можно быстрее добраться из вершины $1$ в вершину $N$, обязательно посетив вершину $K$.

Вы можете выполнить следующее действие «отката» не более одного раза:

• Переместиться в вершину, в которой вы находились $T$ единиц времени назад. Перед выполнением этого действия и после него вы должны находиться в какой-либо вершине. Это действие невозможно выполнить, если с момента старта прошло менее $T$ единиц времени.

Найдите минимальное время, необходимое для перемещения из вершины $1$ в вершину $N$ через вершину $K$ с учетом возможности использования действия «отката» не более одного раза.

Входные данные

В первой строке через пробел заданы количество вершин $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$. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Выходные данные

В первой строке выведите минимальное время, необходимое для перемещения из вершины $1$ в вершину $N$ через вершину $K$. Если такой путь невозможен, выведите -1.

Примеры

Input 1

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

Output 1

6

Input 2

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

Output 2

-1