Вы живёте в городе, состоящем из \(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\).
Так как вы хотите выспаться, вам стало интересно — как поздно вы можете выйти из дома, чтобы успеть поговорить по телефону и при этом не опоздать на мероприятие?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальный момент времени, когда вы можете выйти из дома, чтобы успеть поговорить по телефону и не опоздать на мероприятие. Если вы не можете попасть на мероприятие вовремя, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
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
|