Problems
Сетевые войны
Сетевые войны
Компьютерная сеть Байтландии состоит из \textbf{n} компьютеров, соединенных \textbf{m} оптоволоконными кабелями. Каждый кабель соединяет какие-то два компьютера и может передавать данные в обоих направлениях. Два компьютера сети особенно важны --- один имеет выход в интернет, а другой соединен с президентской резиденцией.
Компьютер, соединенный с президентской резиденцией, имеет номер \textbf{1}, а компьютер, имеющий выход в интернет, --- номер \textbf{n}.
Недавно компания \textit{Max Traffic} решила взять под контроль некоторые соединения, такие чтобы иметь возможность просматривать данные, передаваемые пользователями из президентской резиденции. Конечно же \textit{Max Traffic} хочет контролировать такой набор соединений, чтобы все данные, передаваемые из интернета в президентскую резиденцию, проходили хотя бы через одно из контролируемых соединений.
Чтобы притворить свой план в жизнь, компании необходимо купить соответствующие соединения у их текущих владельцев. Каждое соединение имеет определенную цену. Поскольку основная специализация компании не шпионаж, а предоставление интернет услуг, руководство компании хочет, чтобы средняя цена покупки была минимальна. Если компания покупает \textbf{k} соединений суммарной стоимостью \textbf{c}, то требуется минимизировать значение \textbf{c=k}.
\InputFile
Первая строка входного файла содержит целые числа \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{100}) и \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{400}). Последующие \textbf{m} строк содержат описания соединений --- каждый кабель описывается тремя целыми числами: номерами компьютеров, которые он соединяет, и стоимостью покупки. Стоимость каждого соединения положительна и не превосходит \textbf{10^7}.
Любые два компьютера соединены не более, чем одним кабелем. Никакой компьютер не соединен сам с собой. Гарантируется, что сеть связна, т.е. данные можно передать от любого компьютера до любого другого по проводам сети.
\OutputFile
В первой строке выведите число соединений, которое надо купить. Во второй строке выведите номера этих соединений. Соединения нумеруются начиная с \textbf{1} в том же порядке, в каком они заданы во входном файле.
Input example #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
Output example #1
4 3 4 5 6