e-olymp
Змагання

Spanning Tree + DSU

Сделка с нефтью

Нефть - очень важный стратегический ресурс. Недавно Соединенные Штаты Антарктики вторглись в очень богатую нефтью страну Кари, и теперь стараются держать контроль над ее нефтетранспортной системой. Система состоит из трубопроводов, соединяющих различные узлы - источники нефти и главные города и порты стран. Он сконструирован таким образом, что можно транспортировать нефть из любого узла в любой другой.

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

Для каждого трубопровода террористы знают стоимость взорвать его. Они имеют фиксированную сумму денег и хотят взорвать как можно больше труб на эту сумму. Однако, поскольку им по-прежнему нужна нефть для себя в разных регионах страны, они хотят чтобы система по-прежнему была в состоянии транспортировать нефть из любого узла до любого другого. Помогите им установить, какие трубы следует взорвать.

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

Первая строка содержит количество вершин n, количество трубопроводов m и количество денег s у террористов (2n50000, 1m100000, 0s1018). Следующие m строк содержат информацию о трубопроводах - номера вершин, соединяемые трубопроводом, и стоимость его подрыва (она не превосходит 109).

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

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
6 7 10
1 2 3
1 3 3
2 3 3
3 4 1
4 5 5
5 6 4
4 6 5
Вихідні дані #1
2
1 5
Джерело 2004 Петрозаводск, Лето, Контест Андрея Станкевича 7, Август 22, Задача H