G. Звонок во время пути
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы живёте в городе, состоящем из $$$n$$$ перекрёстков и $$$m$$$ улиц, соединяющих некоторые пары перекрёстков. По каждой улице можно перемещаться в любую сторону. Никакие две улицы не соединяют одну и ту же пару перекрёстков, и никакая улица не соединяет перекрёсток с самим собой. Из любого перекрёстка можно добраться до любого другого, возможно, проходя через какие-то другие перекрёстки.

Каждую минуту вы можете сесть на автобус на перекрёстке $$$u_i$$$ и доехать за $$$l_{i1}$$$ минут до перекрёстка $$$v_i$$$. И наоборот доехать от перекрёстка $$$v_i$$$ до перекрёстка $$$u_i$$$ за $$$l_{i1}$$$ минут. Садиться в автобус и выходить из него можно только на перекрёстках. Сесть в автобус на перекрёстке можно только находясь в нём.

Также по каждой улице можно пройти пешком за $$$l_{i2} > l_{i1}$$$ минут.

Вы можете делать остановки на перекрёстках.

Вы живёте на перекрёстке с номером $$$1$$$. Сегодня вы проснулись в момент времени $$$0$$$, и у вас запланировано важное мероприятие на перекрёстке с номером $$$n$$$, на которое вы должны добраться не позднее момента времени $$$t_0$$$. Также у вас запланирован телефонный звонок, который продлится с $$$t_1$$$ по $$$t_2$$$ минуту ($$$t_1 < t_2 < t_0$$$).

Во время телефонного разговора нельзя ехать на автобусе, но можно идти по любым улицам пешком, сделать остановку или находиться у себя дома. Вы можете выходить из автобуса в минуту $$$t_1$$$ и заходить в автобус в минуту $$$t_2$$$.

Так как вы хотите выспаться, вам стало интересно — как поздно вы можете выйти из дома, чтобы успеть поговорить по телефону и при этом не опоздать на мероприятие?

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 10^5, 1 \le m \le 10^5$$$) — количество перекрёстков и улиц в городе.

Вторая строка описания каждого набора входных данных содержит три целых числа $$$t_0$$$, $$$t_1$$$, $$$t_2$$$ ($$$1 \le t_1 < t_2 < t_0 \le 10^9$$$) — время начала мероприятия, время начала телефонного звонка и время его конца, соответственно.

Следующие $$$m$$$ строк каждого набора данных содержат описания улиц.

$$$i$$$-я строка содержит четыре целых числа $$$u_i$$$, $$$v_i$$$, $$$l_{i1}$$$, $$$l_{i2}$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$, $$$1 \le l_{i1} < l_{i2} \le 10^9$$$) — номера перекрёстков, соединяемых $$$i$$$-й улицей, а также время пути по улице на автобусе и пешком. Гарантируется, что никакие две улицы не соединяют одну и ту же пару перекрёстков, а также что из любого перекрёстка можно добраться до любого другого.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$. Также гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный момент времени, когда вы можете выйти из дома, чтобы успеть поговорить по телефону и не опоздать на мероприятие. Если вы не можете попасть на мероприятие вовремя, выведите -1.

Пример
Входные данные
7
5 5
100 20 80
1 5 30 100
1 2 20 50
2 3 20 50
3 4 20 50
4 5 20 50
2 1
100 50 60
1 2 55 110
4 4
100 40 60
1 2 30 100
2 4 30 100
1 3 20 50
3 4 20 50
3 3
100 80 90
1 2 1 10
2 3 10 50
1 3 20 21
3 2
58 55 57
2 1 1 3
2 3 3 4
2 1
12 9 10
2 1 6 10
5 5
8 5 6
2 1 1 8
2 3 4 8
4 2 2 4
5 3 3 4
4 5 2 6
Выходные данные
0
-1
60
80
53
3
2