Сеть в Байтляндии состоит из n серверов, соединенных m оптическими кабелями. Каждый кабель соединяет два сервера и способен передавать данные в обоих направлениях. Два сервера сети особенно важны - они подключены к глобальной мировой сети и сети президентского дворца соответственно.

Сервер, подключенный к сети президентского дворца, имеет номер 1, а сервер, подключенный к глобальной мировой сети имеет номер n.

Недавно компания Макс Трафик решила взять под контроль некоторые кабеля, вследствие чего она смогла просматривать данные, которые передаются пользователями президентского дворца. Они хотят контролировать такое множество кабелей, что невозможно передать никакие данные из глобальной сети к президентскому дворцу, не передавая их по крайней мере через один из кабелей множества.

Чтобы воплотить свои планы в жизнь, компания должна купить соответствующие кабели у их нынешних владельцев. Каждый кабель имеет некоторую цену. Поскольку основной бизнес компании не шпионаж, а обеспечение подключения к интернету домашних пользователей, то его руководство хочет сделать операцию хорошей инвестицией. Он хочет приобрести такой набор кабелей, средняя стоимость которых минимально возможна.

Таким образом, если компания покупает k кабелей общей стоимостью c, то она хочет минимизировать значение c / k.

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

Первая строка содержит значения n и m (2 ≤ n ≤ 100, 1 ≤ m ≤ 400). Следующие m строк описывают кабеля - каждый кабель задается тремя целыми числами: номерами серверов, которые он соединяет и стоимость кабеля. Стоимость каждого кабеля положительна и не превышает 107.

Любые два сервера соединены не более одним кабелем. Никакой кабель не соединяет сервер сам с собой. Сеть является связной, можно передать данные между любыми двумя серверами.

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

Вывести количество кабелей k, которое следует купить. Далее вывести номера приобретаемых кабелей. Кабеля нумеруются с единицы в порядке, в котором они подаются на вход.