29436번 - Дороги 스페셜 저지다국어

문제

В некой стране есть $n$ городов и $m$ двусторонних дорог, причем по этим дорогам можно добраться из любого города в любой. Каждая дорога в этой стране либо платная, либо бесплатная. За проезд по бесплатной дороге, как следует из названия, %К.О. путешественники не платят ничего, за проезд по платной дороге каждый путешественник платит некую круглую сумму, которая поступает в казну Министерства управления дорогами. Казна тратится на поддержание работоспособности дорог и некоторые другие нужды.

Некоторое время назад Министерством был издан указ об оптимизации дорожного хозяйства страны с целью сокращения той части бюджета, которая тратится на поддержание работоспособности этого самого хозяйства. Единственным разумным способом оптимизации оказалось закрытие нескольких дорог. Конкретнее, было решено оставить во всей стране ровно $n-1$ дорогу таким образом, чтобы из любого города по-прежнему можно было добраться куда угодно. Кроме того, платных дорог среди оставленных должно быть ровно $k$ --- достаточное число, чтобы пополнять казну Министерства и не причинить неудобств народу страны.

Вам поручено разработать генеральный план этой оптимизации, то есть указать, какие именно дороги следует оставить.

입력

Первая строка входного файла содержит три целых числа $n,ドル $m$ и $k$(1ドル \le k < n \le 100000,ドル 1ドル \le m \le 200000$) --- количество городов, количество дорог и количество платных дорог, которые должны остаться. Следующие $m$ строк содержат описания дорог. Описание дороги состоит из трех целых чисел --- $a_i,ドル $b_i$ и $c_i$(1ドル \le a_i, b_i \le n,ドル 0ドル \le c_i\le 1$) --- два города, соединенные этой дорогой, и тип дороги, где 0ドル$ означает, что дорога бесплатна, а 1ドル$ --- что за проезд по ней необходимо платить. Никакая дорога не соединяет город с самим собой, однако два города может соединять более чем одна дорога.

출력

В выходной файл выведите $n - 1$ целых чисел, разделенных пробелами --- номера дорог, которые необходимо оставить. Если ответов несколько --- выведите любой возможный. Номера дорогам присвоены соответственно порядку, в котором они даны во входном файле, дороги нумеруются с 1. Если решения не существует, выведите единственное число <<$-1$>>

제한

힌트