Problem description

Paulina zdała ostatnio egzamin na prawo jazdy, a już jest zmuszona do jeżdżenia po autostradzie. Jej zadaniem jest przewiezienie paczek z prezentami świątecznymi z miasta A do miasta B. Zgodnie z prawem, może przejechać maksymalnie K kilometrów bez przerwy. Po osiągnięciu tego limitu musi zrobić postój trwający co najmniej P minut, zanim będzie mogła kontynuować jazdę. Z racji tego, że pojazd, którym się porusza, nie jest pierwszej młodości, może poruszać się z maksymalną prędkością jednego kilometra na minutę.

Święta już za rogiem, więc Paulina chciałaby przejechać trasę jak najszybciej. Jako jej kolega programista odpowiedz na jej pytanie, po ilu minutach najszybciej może dojechać z miasta A do miasta B, wiedząc, że postoje może robić jedynie w miastach oraz znając długości dróg łączących pary miast.

Wejście

W pierwszym wierszu wejścia znajdują się liczby naturalne N, M, A, B, K i P oznaczające odpowiednio liczbę miast, liczbę dróg, miasto, z którego chce wyruszyć Paulina oraz miasto, do którego chce dojechać, maksymalną liczbę kilometrów, którą można przejechać bez postoju oraz minimalną długość postoju w minutach.

W każdym z kolejnych M wierszy znajdują się trzy liczby X_i, Y_i oraz Z_i oznaczające drogę z miasta X_i do miasta Y_i o długości Z_i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinien znaleźć się najkrótszy czas przejechania z miasta A do miasta B bez łamania prawa lub NIE jeżeli się nie da.

Ograniczenia

1 ≤ N, M ≤ 500 000, 1 ≤ A, B, X_i, Y_i ≤ N, 1 ≤ K, P, Z_i ≤ 1 000 000.

Przykład

6 6 4 6 4 5
5 3 6
4 3 5
4 1 2
5 1 3
6 5 4
1 3 3

19