E. Андрей и такси
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Мэр города решил поменять направления некоторых дорог таким образом, чтобы таксист больше не смог бесконечно увеличивать счетчик клиента. Другими словами, таксист, находящийся на конкретном перекрестке, не мог бы попасть на него повторно, совершив ненулевой маршрут.

Для того, чтобы поменять направление дороги, нужны регулировщики. Для каждой конкретной дороги известно, сколько регулировщиков нужно, чтобы поменять направление дороги на противоположное. Разрешено менять направление дорог последовательно, то есть одни и те же регулировщики могут поучаствовать в изменении нескольких дорог.

Необходимо вычислить минимальное количество регулировщиков, необходимых для выполнения задания, и список дорог, у которых необходимо поменять направление.

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

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 100\,000$$$, $$$1 \leq m \leq 100\,000$$$) — количество перекрестков в городе и количество дорог, соответственно.

В каждой из следующих $$$m$$$ строк содержатся три целых числа $$$u_{i}$$$, $$$v_{i}$$$ и $$$c_{i}$$$ ($$$1 \leq u_{i}, v_{i} \leq n$$$, $$$1 \leq c_{i} \leq 10^9$$$, $$$u_{i} \ne v_{i}$$$) — номер перекрестка, на котором дорога начинается, номер перекрестка, где она заканчивается и количество регулировщиков, необходимых для изменения направления этой дороги.

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

В первой строке выведите два целых числа — минимальное число регулировщиков, необходимых для выполнения задания и количество дорог $$$k$$$, у которых необходимо поменять направление. $$$k$$$ не должно быть минимальным.

В следующей строке через пробел выведите $$$k$$$ целых чисел — номера дорог, у которых необходимо поменять направление. Дороги нумеруются с $$$1$$$ в порядке следования во входных данных. Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4
Выходные данные
2 2
1 3
Входные данные
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3
Выходные данные
3 3
3 4 7
Примечание

В первом примере имеется два простых цикла: $$$1 \rightarrow 5 \rightarrow 2 \rightarrow 1$$$ и $$$2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$$$. Один регулировщик сможет развернуть только дорогу $$$2 \rightarrow 1$$$, второй цикл в одиночку он разрушить не сможет. Два регулировщика уже смогут развернуть дороги $$$2 \rightarrow 1$$$ и $$$2 \rightarrow 3$$$, после чего не останется перекрестка, на который можно попасть снова, совершив ненулевой маршрут.

Во втором примере одного регулировщика недостаточно, чтобы разрушить маршрут $$$ 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 $$$. С помощью трёх регулировщиков можно, например, развернуть дороги $$$1 \rightarrow 3$$$ ,$$$ 2 \rightarrow 4$$$, $$$1 \rightarrow 5$$$.