Квест
Во время квеста в ЛКШ-2017 преподаватели дали школьникам такое задание. Каждый из n преподавателей задумал число. Школьник может поймать двух преподавателей и спросить об их числах. В ответ они сообщают школьнику наибольший общий делитель задуманных ими чисел.
Школьники опросили m пар преподавателей. Помогите школьникам выяснить числа, задуманные преподавателями.
Входные данные
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n ≤ 10, 0 ≤ m ≤ 45). Следующие m строк содержат по три целых числа: i, j и d - такая тройка означает, что наибольший общий делитель чисел, загаданных i-м и j-м преподавателями равен d (1 ≤ d ≤ 100). Для каждых двух i и j дано не более 1-го d. Преподаватели нумеруются от 1 до n.
Выходные данные
Если решения не существует, выведите в выходной файл слово impossible. Иначе выведите n целых чисел - числа, задуманные преподавателями. Каждое число должно быть положительным и не превышать 10^18. Если решений несколько, выведите любое.