Se tiene un grafo simple que consta de $N$ vértices numerados del $1$ al $N$ y $M$ aristas ponderadas no dirigidas.

Al moverse entre dos vértices utilizando una arista, el tiempo requerido es igual al peso de dicha arista. Por ejemplo, si una arista tiene un peso de 3, se tardan 3 horas en recorrerla. Durante el movimiento, no se está en ningún vértice. También es posible permanecer en un vértice sin utilizar ninguna arista para dejar pasar el tiempo.

Debes viajar desde el vértice $1$ hasta el vértice $N$, pasando obligatoriamente por el vértice $K$, en el menor tiempo posible.

Puedes realizar la siguiente acción de regresión como máximo una vez:

• Moverse al vértice donde te encontrabas hace $T$ unidades de tiempo. Debes estar en un vértice tanto antes como después de realizar este movimiento. Esta acción no puede realizarse si no han transcurrido al menos $T$ unidades de tiempo desde el inicio.

Calcula el tiempo mínimo necesario para viajar desde el vértice $1$ hasta el vértice $N$ pasando por el vértice $K$, considerando que puedes utilizar la acción de regresión como máximo una vez.

Entrada

La primera línea contiene el número de vértices $N$, el número de aristas $M$, el número del vértice por el que se debe pasar $K$ y el valor $T$, separados por espacios. $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

Desde la segunda línea y durante $M$ líneas, se proporcionan los dos vértices $u$ y $v$ que conecta cada arista, junto con su peso $c$, separados por espacios. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Salida

En la primera línea, imprime el tiempo mínimo necesario para viajar desde el vértice $1$ hasta el vértice $N$ pasando por el vértice $K$. Si dicho recorrido no es posible, imprime -1 en su lugar.

Ejemplos

Entrada 1

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

Salida 1

6

Entrada 2

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

Salida 2

-1