eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сетевые войны

Сетевые войны

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Приклад

Вхідні дані #1
6 8
1 2 3
1 3 3
2 4 2
2 5 2
3 4 2
3 5 2
5 6 3
4 6 3
Вихідні дані #1
4
3 4 5 6
Джерело 2004 Петрозаводск, Лето, Контест Андрея Станкевича 7, Август 22, Задача G