F. Загрязненная кухня Аркадия
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аркадий очень любит гулять по своей кухне. Его запутанная кухня состоит из нескольких важных мест, соединенных проходами. К сожалению, часто эти проходы оказываются залиты молоком так, что пройти по ним нельзя. А именно, по каждому проходу можно ходить лишь в определенный отрезок времени, в любую сторону.

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

Сегодня Аркадию понадобилось срочно пройти от места 1 до места n на своей кухне. Он хочет выйти в момент времени 0 из места 1 и как можно быстрее оказаться в месте n. Помогите ему найти минимальное время, которое он должен затратить на путь.

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

В первой строке находятся два целых числа n и m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105) — количество важных мест и проходов, соответственно.

Далее следуют m строк, каждая описывает один проход. Каждая строка содержит четыре целых числа a, b, l и r (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ l < r ≤ 109) — места, которые соединяет этот проход, и отрезок времени, в течение которого можно по нему передвигаться.

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

Выведите одно число — минимальное время, которое Аркадий должен затратить на путь. Если он не может добраться до места n, выведите -1.

Примеры
Входные данные
5 6
1 2 0 1
2 5 2 3
2 5 0 1
1 3 0 1
3 4 1 2
4 5 2 3
Выходные данные
3
Входные данные
2 1
1 2 1 100
Выходные данные
-1
Примечание

В первом примере Аркадий должен пройти через важные места 1 → 3 → 4 → 5.

Во втором примере Аркадий не может начать свой путь, так как в момент времени 0 единственный проход залит молоком.