Час зустрічі (Бронза)
Бессі та її сестра Елсі хочуть вирушити з амбару на своє улюблене поле так, щоб вони одночасно залишили амбар і прибули на улюблене поле.
Ферма складається з 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, то вони прибудуть одночасно.