Dany jest graf prosty składający się z $N$ wierzchołków ponumerowanych od $1$ do $N$ oraz $M$ nieskierowanych krawędzi ważonych.

Przemieszczanie się między dwoma wierzchołkami za pomocą krawędzi zajmuje czas równy wadze tej krawędzi. Na przykład, przejście krawędzią o wadze 3 zajmuje 3 jednostki czasu. W trakcie przemieszczania się nie znajdujesz się w żadnym wierzchołku. Możesz również spędzać czas, pozostając w wierzchołku bez korzystania z krawędzi.

Twoim celem jest jak najszybsze dotarcie z wierzchołka $1$ do wierzchołka $N$, przechodząc po drodze przez wierzchołek $K$.

Możesz wykonać następującą akcję cofnięcia maksymalnie jeden raz:

• Przenieś się do wierzchołka, w którym znajdowałeś się $T$ jednostek czasu temu. Zarówno przed, jak i po wykonaniu tej akcji musisz znajdować się w wierzchołku. Nie możesz wykonać tej akcji, jeśli od momentu startu nie upłynęło jeszcze $T$ jednostek czasu.

Oblicz minimalny czas potrzebny na dotarcie z wierzchołka $1$ do wierzchołka $N$ przez wierzchołek $K$, mając możliwość wykonania akcji cofnięcia maksymalnie jeden raz.

Wejście

W pierwszej linii podano liczbę wierzchołków $N$, liczbę krawędzi $M$, numer wierzchołka, przez który należy przejść $K$, oraz wartość $T$, oddzielone spacjami. $(3 \le N \le 10^5;$ $0 \le M \le 10^5;$ $2 \le K \le N-1;$ $1 \le T \le 10^9)$

W kolejnych $M$ liniach podano opisy krawędzi. Każda linia zawiera numery dwóch wierzchołków $u$ i $v$ oraz wagę $c$, oddzielone spacjami. $(1 \le u, v \le N;$ $u \neq v;$ $0 \le c \le 10^5)$

Wyjście

W pierwszej linii wypisz minimalny czas potrzebny na dotarcie z wierzchołka $1$ do wierzchołka $N$ przez wierzchołek $K$. Jeśli takie przejście jest niemożliwe, wypisz -1.

Przykład

Wejście 1

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

Wyjście 1

6

Wejście 2

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

Wyjście 2

-1