Il existe un graphe simple composé de $N$ sommets numérotés de $1$ à $N$ et de $M$ arêtes pondérées non orientées.

Le déplacement entre deux sommets via une arête prend un temps égal au poids de l'arête. Par exemple, traverser une arête de poids 3 prend 3 unités de temps. Pendant le déplacement, vous n'êtes sur aucun sommet. Il est également possible de rester immobile sur un sommet pour passer le temps sans utiliser d'arête.

Vous devez vous déplacer du sommet $1$ vers le sommet $N$ en passant par le sommet $K$ le plus rapidement possible.

Vous pouvez effectuer l'action de régression suivante au maximum une fois :

• Se déplacer vers le sommet où vous étiez il y a $T$ unités de temps. Vous devez être sur un sommet avant et après ce déplacement. Cette action est impossible si $T$ unités de temps ne se sont pas encore écoulées depuis le départ.

Calculez le temps minimum nécessaire pour aller du sommet $1$ au sommet $N$ en passant par le sommet $K$, en sachant que vous pouvez utiliser l'action de régression au maximum une fois.

Entrée

La première ligne contient le nombre de sommets $N$, le nombre d'arêtes $M$, le numéro du sommet à visiter $K$, et la valeur $T$, séparés par des espaces. $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

À partir de la deuxième ligne, $M$ lignes suivent, chacune contenant les numéros des deux sommets $u$ et $v$ reliés par l'arête, ainsi que son poids $c$, séparés par des espaces. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Sortie

Affichez sur la première ligne le temps minimum nécessaire pour se déplacer du sommet $1$ au sommet $N$ en passant par le sommet $K$. Si un tel déplacement est impossible, affichez -1.

Exemples

Entrée 1

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

Sortie 1

6

Entrée 2

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

Sortie 2

-1