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

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

Компьютер, соединенный с президентской резиденцией, имеет номер 1, а компьютер, имеющий выход в интернет, — номер n.

Недавно компания Max Traffic решила взять под контроль некоторые соединения, такие чтобы иметь возможность просматривать данные, передаваемые пользователями из президентской резиденции. Конечно же Max Traffic хочет контролировать такой набор соединений, чтобы все данные, передаваемые из интернета в президентскую резиденцию, проходили хотя бы через одно из контролируемых соединений.

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

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

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

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

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

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

Пример

Входные данные #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