Bessie и её сестра Elsie хотят отправиться из хлева на любимое поле, выйдя строго одновременно и прибыв строго одновременно.

На ферме $N$ полей ($1 \leq N \leq 100$) с номерами $1 \dots N$: на $1$ хлев, $N$ любимое. Ферма на склоне: поле $X$ выше $Y$, если $X < Y$. $M$ троп соединяют пары полей, но из-за крутизны идти можно лишь вниз. Например, между $5$ и $8$ можно идти $5 \to 8$, но не обратно, ведь это вверх. Между парой не более одной тропы, поэтому $M \leq N(N-1)/2$.

Время на тропе может различаться: например, у Bessie $10$ единиц, у Elsie $20$. Время тратится только на тропах между полями: они спешат, проходят поля практически за нулевое время и нигде не ждут.

Определите минимальное время, чтобы обе прибыли на любимое поле строго одновременно.

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

Первая строка содержит $N$ и $M$ через пробел.

Следующие $M$ строк задают тропы четырьмя целыми $A$ $B$ $C$ $D$: $A$ и $B$ ($A < B$) — соединённые поля, $C$ — время Bessie, $D$ — время Elsie. Оба $C$ и $D$ в диапазоне $1 \ldots 100$.

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

Выведите одно целое — минимальное время одновременного прибытия. Если это невозможно или Bessie либо Elsie вообще не может добраться до любимого поля, выведите IMPOSSIBLE одной строкой.

Примеры

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

3 3
1 3 1 2
1 2 1 2
2 3 1 2

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

2

Примечание

Bessie вдвое быстрее Elsie на каждой тропе, но при маршрутах $1 \to 2 \to 3$ для Bessie и $1 \to 3$ для Elsie они прибудут одновременно.

Автор задачи: Nick Wu, 2015