Бесси и ее сестра Элси хотят отправиться из амбара на свое любимое поле так, чтобы они вышли из амбара в одно и то же время, а также точно в то же время прибыли на свое любимое поле.

Ферма представляет собой набор из n полей, пронумерованных 1..n, где поле 1 содержит сарай, а поле n - любимое поле. Ферма построена на склоне холма, при этом поле x находится выше по высоте, чем поле y, если x < y. Набор m путей соединяет пары полей. Однако, поскольку каждая тропа довольно крутая, по ней можно следовать только в направлении спуска. Например, путь, соединяющий поле 5 с полем 8, можно пройти в направлении 5 -> 8, но не в обратном направлении, так как это будет в гору. Каждая пара полей связана не более чем одним путем, поэтому m ≤ n * (n - 1) / 2.

Бесси и Элси может потребоваться разное количество времени, чтобы пройти по пути; например, Бесси может потребоваться 10 единиц времени, а Элси - 20. Более того, Бесси и Элси тратят время только на перемещение по дорожкам между полями - поскольку они спешат, то всегда путешествуют по полю практически за нулевое время, никогда нигде не ожидая.

Определите кратчайшее время, которое потребуется Бесси и Элси, чтобы добраться до своего любимого поля в одно и то же время.

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

Первая строка содержит n (1 ≤ n ≤ 16) и m.

Каждая из следующих m строк описывает путь, используя четыре целых числа A B C D, где A и B (где A < B) поля, соединенные путем, C — время, необходимое Бесси, чтобы пройти по пути, а D — время, необходимое Элси, чтобы пройти путь. И C, и D находятся в диапазоне 1..1000.

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

Выведите одно целое число, задающее минимальное время, необходимое Бесси и Элси, чтобы добраться до их любимого поля и прибыть в одно и то же время. Если это невозможно или если Бесси или Элси вообще не могут добраться до поля избранного, выведите слово IMPOSSIBLE в одной строке.

Пример

Бесси в два раза быстрее Элси на каждом пути, но если Бесси выбирает путь 1 -> 2 -> 3, а Элси выбирает путь 1 -> 3 то они прибудут одновременно.