Час зустрічі (Срібло)
Бессі та її сестра Ельза хочуть подорожувати від сараю до улюбленого поля так, щоб вирушити одночасно від сараю і прибути одночасно до улюбленого поля.
Ферма складається з n полів, пронумерованих від 1 до n, де поле 1 містить сарай, а поле n — це улюблене поле. Ферма розташована на схилі пагорба, причому поле x розташоване вище за висотою, ніж поле y, якщо x < y. Існує m шляхів, які з'єднують пари полів. Однак, оскільки кожна стежка досить крута, по ній можна рухатися лише в напрямку спуску. Наприклад, шлях, що з'єднує поле 5 з полем 8, можна пройти в напрямку 5 -> 8, але не в зворотному напрямку, оскільки це буде вгору. Кожна пара полів з'єднана не більше ніж одним шляхом, тому m ≤ n * (n - 1) / 2.
Бессі та Ельзі може знадобитися різний час, щоб пройти шлях; наприклад, Бессі може знадобитися 10 одиниць часу, а Ельзі - 20. Крім того, Бессі та Ельза витрачають час лише на переміщення по стежках між полями — оскільки вони поспішають, то завжди подорожують по полю практично за нульовий час, ніколи ніде не чекаючи.
Визначте найкоротший час, який знадобиться Бессі та Ельзі, щоб дістатися до свого улюбленого поля одночасно.
Вхідні дані
Перший рядок містить n (1 ≤ n ≤ 100) і m.
Кожен з наступних m рядків описує шлях, використовуючи чотири цілі числа A B C D, де A і B (де A < B) — це поля, з'єднані шляхом, C — час, необхідний Бессі, щоб пройти шлях, а D — час, необхідний Ельзі, щоб пройти шлях. І C, і D знаходяться в діапазоні 1..100.
Вихідні дані
Виведіть одне ціле число, що визначає мінімальний час, необхідний Бессі та Ельзі, щоб дістатися до їх улюбленого поля і прибути одночасно. Якщо це неможливо або якщо Бессі чи Ельза взагалі не можуть дістатися до улюбленого поля, виведіть слово IMPOSSIBLE в одному рядку.
Приклад
Бессі вдвічі швидша за Ельзу на кожному шляху, але якщо Бессі обирає шлях 1 -> 2 -> 3, а Ельза обирає шлях 1 -> 3, то вони прибудуть одночасно.