Завдання

У більшості рецептів деякі дії потрібно виконувати перед іншими. Якщо для кожного завдання у нас є список інших завдань, від яких воно залежить, ми можемо скласти розклад, що приведе нас до чудової страви. Багато хто знає, що таке завдання можна вирішити за допомогою топологічного сортування.

Але життя не завжди таке просте. Наприклад, розглянемо рецепт приготування тіста для піци:

1. Змішайте дріжджі з теплою водою, почекайте від 5 до 10 хвилин.

2. Мішайте інші інгредієнти від 7 до 9 хвилин.

3. Змішайте дріжджі та інші інгредієнти від 10 до 15 хвилин.

4. Почекати від 90 до 120 хвилин, поки тісто не підійде.

5. Замісити тісто і дати йому відстоятися від 10 до 15 хвилин.

6. Розкатати тісто.

Наприклад, завдання 1 і 2 можуть виконуватися одразу після першої хвилини (ми завжди використовуємо першу хвилину на читання рецепта і планування роботи). Завдання 3 можна почати найраніше на 8-ій хвилині, а завдання 4 можна почати лише на 18-ій хвилині після старту, і так далі. Це простий розклад. Але якщо деякі завдання мають багато залежностей, складання розкладу стає досить складним завданням. Іноді навіть рецепт неможливо виконати. Наприклад, розглянемо наступний абстрактний рецепт:

1. завдання 1

2. після завдання 1, але протягом 2 хвилин після його початку, виконати завдання 2

3. як мінімум через 3 хвилини після початку завдання 2, але протягом 2 хвилин після початку завдання 1, виконати завдання 3

У вас є набір завдань. Завдання залежать одне від одного залежно від часу їх початку. Вам потрібно призначити час початку для кожного завдання так, щоб задовольнити всі задані умови, або повідомити про неможливість їх виконання.

Вхідні дані

Складається з декількох тестів. Перша стрічка кожного тесту містить кількість завдань n, (1 ≤ n ≤ 100). Наступний рядок містить невід'ємне ціле число m - кількість обмежень. Кожен з наступних m рядків описує обмеження. Вони можуть бути двох типів:

завдання i починається як мінімум через A хвилин після початку завдання j завдання i починається протягом A хвилин після початку завдання j

де i і j - номери двох різних завдань (1 ≤ i, j ≤ n), а A - невід'ємне ціле число (A ≤ 150). Перше обмеження стверджує, що завдання i може початися як мінімум через A хвилин після початку завдання j. Друге обмеження говорить про те, що завдання i повинно початися не раніше початку завдання j, і протягом A хвилин після початку завдання j. На одну і ту ж пару завдань можуть накладатися кілька обмежень. Зазначимо, що в умовах "як мінімум" і "протягом" межі часових інтервалів включаються (тобто якщо завдання 1 починається в 1 хвилину, а завдання 2 стартує в 4 хвилину, то завдання 2 стартує як мінімум через 3 хвилини після завдання 1, і протягом 3 хвилин після початку завдання 1).

Вхідні дані закінчуються, коли n = 0.

Вихідні дані

Для кожного тесту в окремому рядку виведіть часи початку завдань з 1 по n, розділяючи одним пробілом. Кожне число повинно вказувати хвилину, в яку відповідне завдання почнеться. Час початку кожного завдання повинен бути позитивним і меншим 1000000. Шуканих допустимих розкладів може бути декілька, вам слід вивести будь-який з них. Якщо розкладу, що задовольняє всі обмеження, не існує, виведіть Impossible. в окремому рядку.

Приклади