Вечеря#3415

Вечеря

1 секунда

64 мегабайти

Складна

Ось вже декілька років північна конференція практичної комбінаторики (NCPC) збирає все більшу кількість учасників. У цьому році команда організаторів очікує рекордної кількості учасників. У зв'язку з політикою організації цього престижного заходу на сайті конференції давно повідомлено, що вона буде проходити у Гранд Готелі в Стокгольмі. У готелі є два великих зали для обідів, але, на жаль, у кожен з цих залів може поміститися лише до $2/3$ учасників NCPC, тож учасникам доведеться бути розділеними на дві групи.

Це обмеження вимагає деякого творчого мислення організаторів для участі усіх команд під час конференції на вечері: вони можуть розділити учасників на дві частини, кожна з яких не більша за $2/3$ від усієї групи. Під час зустрічі застосовуються деякі оригінальні правила поділу на групи, щоб під час вечері вони могли розповідати іншим учасникам про свої захоплення. Нарешті, доки є деякі строгі правила логіки, згідно з якими можна визначити, у якому з двох обідніх залів ви будете сидіти, ви (як математик) були б від цього лише щасливі! Після деяких роздумів їм спала наступна ідея для поділу учасників: вибрати такий мінімальний рік $Y$ для поділу учасників на дві частини, що кожна пара у першій частині зустрілася вперше до року $Y$ , а кожна пара у другій частині зустрілася вперше у році $Y$ або після року $Y$ . Було вирішено чітко кваліфікувати це твердження як відповідне правило для усіх, але виникло логічне запитання: а чи буде це можливо?

Вхідні дані

Перший рядок вхідного файлу містить цілі числа $4 \leq n \leq 400$ 4 \leq n \leq 400 — кількість учасників, і $c$ — кількість відомих перших зустрічей. Кожен з наступних $c$ рядків має формат $a b y$ , тобто учасники $a$ та $b$ ( $1 \leq a < b \leq n$ 1 \leq a < b \leq n) зустрілися вперше у рік $y$ ( $1948 \leq y < 2008$ 1948 \leq y < 2008). Жодна пара учасників не зустрічається у списку більше ніж один раз, також немає у списку пар, які, як припускається, вперше зустрічаються лише зараз (поточний рік $2008$ ).

Вихідні дані

Для кожного тесту виведіть або найменший рік $Y$ такий, що можна розділити учасників на дві частини, жодна з яких не містить більше $2 n /3$ людей, таких, що усі люди у першій частині вперше зустрілися до року $Y$ , а усі люди у другій частині вперше зустрілися у рік $Y$ чи після року $Y$ . Якщо такого року немає, виведіть "Impossible".

Приклади

Приклад 1