Ян работает в рейтинговом агентстве, которое публикует рейтинги лучших университетов. Ирен — журналистка, которая планирует написать скандальную статью о предстоящем рейтинге.

С помощью различных методов социальной инженерии (не будем вдаваться в подробности) Ирэн получила некоторую инсайдерскую информацию от Яна.

В частности, Ирина получила несколько троек (ai, bi, ci), что означает, что в предстоящем рейтинге университет bi стоит между университетами ai и ci. То есть либо ai идет перед bi, который идет перед ci, либо наоборот. Все тройки, указанные Яном, непротиворечивы - допустим, реальный рейтинг их всех удовлетворяет.

Чтобы начать работу над первым наброском будущей статьи, Ирен необходимо увидеть хоть какое-то приближение к реальному рейтингу. Она попросила Вас найти предложение рейтинга, в котором удовлетворяется хотя бы половина троек, известных Ирэн.

Входные данные

В первой строке записаны целые числа n и m (3 ≤ n ≤ 105, 1 ≤ m ≤ 105), количество включенных в рейтинг университетов и количество троек, которые дал Ирине Ян.

Каждая из следующих m строк содержит три различных целых числа (1 ≤ ai, bi, ci ≤ n) — университеты, задающие тройку.

Выходные данные

Выведите предлагаемый рейтинг от первого университета к последнему. Предложенный рейтинг должен удовлетворить не менее m / 2 тройкам. Если таких предложений несколько, выведите любое из них.

Пример

В примере первые две тройки выполняются, а последняя — нет. Следовательно, по крайней мере половина всех троек удовлетворена.