Задача: Рейсы во времени

Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.

В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте \(B\) как можно раньше (то есть в наименьший возможный момент времени).

При этом разрешается делать пересадки с одного рейса на другой. Если вы прибываете в некоторый пункт в момент времени \(T\), то вы можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени \(T\) или позднее (но не раньше).

Формат входных данных
Первая строка содержит число \(N\) — количество населенных пунктов (\(1 \le N \le 1000\)). Вторая строка содержит два числа \(A\) и \(B\) — номера начального и конечного пунктов. Третья строка содержит число \(K\) — количество рейсов (\(0 \le K \le 1000\)). Следующие \(K\) строк содержит описания рейсов, по одному на строке. Каждое описание представляет собой четверку целых чисел. Первое число каждой четверки задает номер пункта отправления, второе — время отправления, третье — пункт назначения, четвертое — время прибытия. Номера пунктов — натуральные числа из диапазона от 1 до \(N\). Пункт назначения и пункт отправления могут совпадать. Время измеряется в некоторых абсолютных единицах и задается целым числом, по модулю не превышающим \(10^9\). Поскольку рейсы совершаются на машинах времени, то время прибытия может быть как больше времени отправления, так и меньше, или равным ему.

Гарантируется, что входные данные таковы, что добраться из пункта \(A\) в пункт \(B\) всегда можно.

Формат выходных данных
Выведите минимальное время, когда вы сможете оказаться в пункте \(B\).

Ваш ответ: