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

В стране Берляндии n городов. Они пронумерованы целыми числами от 1 до n. Город номер 1 является столицей государства. Между некоторыми парами городов проложены дороги с односторонним движением, однако не все из них находятся в хорошем состоянии. Про каждую дорогу известно, нуждается ли она в ремонте. Если дорога нуждается в ремонте, то проезд по ней запрещен. Однако правительство Берляндии может отремонтировать дорогу и возобновить проезд по ней.

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

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

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

В первой строке через пробел заданы два целых числа n и m (1 ≤ n, m ≤ 105) — количество городов и количество дорог в Берляндии.

В следующих m строках через пробел заданы три целых числа ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 0 ≤ ci ≤ 1), обозначающие дорогу из города ai в город bi. Если ci равно 0, то данная дорога находится в хорошем состоянии, если ci равно 1, то она нуждается в ремонте.

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

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

Если даже после ремонта всех дорог из столицы нельзя добраться до какого-нибудь из городов, то выведите -1. В противном случае в первую строку выведите минимальное количество дорог, которые нужно отремонтировать, а во вторую строку выведите номера этих дорог через одиночные пробелы.

Дороги нумеруются, начиная с 1, в том порядке, в котором они заданы во входном файле.

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

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

Примеры
Входные данные
3 2
1 3 0
3 2 1
Выходные данные
1
2
Входные данные
4 4
2 3 0
3 4 0
4 1 0
4 2 1
Выходные данные
-1
Входные данные
4 3
1 2 0
1 3 0
1 4 0
Выходные данные
0