Жизнь завода по производству олимпиадных задач монотонна и однообразна: каждый день происходит одно и то же, вечера похожи как две снежинки и каждое утро всё начинается сначала - ничего не меняется на заводе по производству олимпиадных задач.

В частности, давно известно, когда в течение дня пара сотрудников встречается между собой. При встрече сотрудники делятся друг с другом новостями.

Утром перед работой сотрудник номер 1 узнал нежелательную новость. Конечно же, он делится с ней при встрече со всеми остальными сотрудниками и они тоже узнают новость и начинаются делиться ей с другими. Если встречаются два сотрудника и один из них знает новость, то начиная с этого момента второй из них также знает новость. Ни один сотрудник не может встречаться с двумя или более сотрудниками одновременно (из соображений секретности). Пара сотрудников может встречаться несколько раз в течение дня. Вы можете помешать ровно одной встрече за весь день. Выберите такую встречу, отмена которой приведёт к тому, что как можно меньше сотрудников завода узнают новость.

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

В первой строке входного файла задано два целых числа $n$ ($2 \le n \le 1000$) и $D$ ($1 \le D \le 100000$) — количество сотрудников и встреч соответственно. В следующих $D$ строках заданы описания встреч. Каждое описание встречи состоит из трех чисел $A_i$, $B_i$ и $T_i$ ($1 \le A_i, Bi \le n, 1 \le T_i \le 10_9$) — пара номеров сотрудников и время встречи.

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

Выведите описание встречи, которую необходимо отменить в том же формате, который используется во входных данных. Если ответов несколько — выведите любой.

Подзадачи