29234번 - Путешествие 다국어

문제

После того, как Остап Бендер в очередной раз упустил Александра Ивановича Корейко, он решил взять ситуацию в свои руки. Расставшись со своей командой и удобной во всех отношениях Антилопой Гну, Остап решил подойти к проблеме с умом.

Господин Корейко, дабы не показывать своего состояния, решил убежать от Остапа, передвигась по стране исключительно на поездах. Однако, поскольку железнодорожная сеть в нашей стране черезвычайно запутана, для того, чтобы добраться до конечного пункта назначения, иногда приходится делать пересадки. Известно, что в железнодорожную сеть входит $n$ станций. Между некоторыми станциями есть двусторонние поезда. У каждого поезда есть своя цена.

После длительных размышлений, Остап понял, что, для конспирации, его подопечный путешествовал по стране по следующему правилу: сначала он передвигался по маршрутам, цена которых не превышала $A$. Затем, когда все стали думать, что господин Корейко совершенно не богат, он решил путешествовать с комфортом. Александр Иванович решил передвигаться по стране маршрутами ценой не менее $B$. Но все подпольные миллионеры ужасно скупы. Известно, что он затратил минимальное количество средств. Так же известно, что Корейко выехал со станции с номером $s$ и приехал на станцию с номером $t$.

Остап хочет узнать, насколько уменьшилось состояние Александра Ивановича в результате этого путешествия.

입력

В первой строке входного файла даны числа $n$ и $m$ (1ドル \le n, m \le 10^5$) --- количество станций и поездов. Во второй строке даны два числа $s, t$ (1ドル \le s, t \le 10^5$) В следующих $m$ строках дано описание маршрутов: $a, b, c$ (1ドル \le a, b \le n,ドル 1ドル \le c \le 10^9$) --- номера станций, соединенных маршрутом, и стоимость маршрута. В последней строке даны два числа $A, B$ (1ドル \le A, B \le 10^9$).

출력

В единственной строке выходного файла выведите ответ на задачу. Если такого пути не существует, выведите -1.

제한

힌트