Codeforces Round 966 (Div. 3) |
---|
Закончено |
Вы живёте в городе, состоящем из $$$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.
75 5100 20 801 5 30 1001 2 20 502 3 20 503 4 20 504 5 20 502 1100 50 601 2 55 1104 4100 40 601 2 30 1002 4 30 1001 3 20 503 4 20 503 3100 80 901 2 1 102 3 10 501 3 20 213 258 55 572 1 1 32 3 3 42 112 9 102 1 6 105 58 5 62 1 1 82 3 4 84 2 2 45 3 3 44 5 2 6
0 -1 60 80 53 3 2
Название |
---|