У 2163 році були виявілені черв'якові діри. Черв'якова діра являє собою тунель крізь простір і час, який з'єднує дві зіркові системи. Ці діри мають наступні властивості:

• Черв'якові діри є односторонніми.
• Час подорожі по довільному тунелю рівний нулю.
• Чер'вякова діра має два кінці, кожен з яких знаходиться у зірковій системі.
• Зіркова система у своїх межах може мати декілька кінців черв'якових дір.
• З деякої невідомої причини починаючи від нашої Сонячної системи завжди можна досягнути довільну іншу зіркову систему переміщуючись деякою послідовністю черв'якових дір (можливо, це тому що Земля є центром універсуму).
• Між довільною парою зіркових систем існує не більше однієї черв'якової діри у довільному з напрямків.
• Обидва кінца черв'якової діри не можуть знаходитись у одній зірковій системі.
• Кожна черв'якова діра переміщує мандрівника на певну константноу кількість років вперед або назад. Наприклад, одна діра може перемістити на 15 років у майбутнє, а інша на 42 роки в минуле.

Відомий фізик, який живе на Землі, хоче використовувати черв'якові діри для дослідження теорії Великого Вибуху. Оскільки двигун викривлення простору ще не винайдено, неможливо напряму подорожувати між зірковими системами. Проте це можна зробити при допомозі черв'якових дір.

Вчений хоче досягнути циклу черв'якових дір, який допоможе йому потрапити у минуле. Рухаючись по цьому циклу декілька разів, можна прийти до часу, коли мав місце Великий Вибух і спостерігати його на власні очі. Напишіть програму, яка визначає існування такого циклу.

Вхідні дані

Перший рядок містить кількість зіркових систем n (1 ≤ n ≤ 1000) і кількість черв'якових дір m (0 ≤ m ≤ 2000). Зіркові системи пронумеровані від 0 (наша сонячна система) до n - 1. Кожна черв'якова двра описується в окремому рядку і містить три цілих числа x, y і t. Ці числа вказують на можливість пересування з зіркової системи з номером x у зіркову систему з номером y, при цьому час змінюється на t (-1000 ≤ t ≤ 1000) років.

Вихідні дані

Рядок містить інформацію, чи можливо у заданій множині систем потрапити у мінус нескінченність у часі використовуючи черв'якові діри. Виводити потріьно рядок "possible" або "not possible".