Угода з нафтою#5668
Нафта є дуже важливим стратегічним ресурсом. Нещодавно багата на нафту країна Карі вирішила модернізувати та підвищити ефективність своєї системи транспортування нафти. Система складається з нафтопроводів, що з'єднують різні вузли — пункти видобутку нафти, головні міста країни та порти. Мережа нафтопроводів спроектована так, щоб можна було транспортувати нафту з будь-якого вузла до будь-якого іншого.
Для забезпечення надійності системи та мінімізації можливих простоїв інженерна команда визначила нафтопроводи, які тимчасово можна вивести з ладу для проведення технічного обслуговування чи модернізації. Кожен нафтопровід можна тимчасово вимкнути за певну вартість обслуговування. Інженерна команда має фіксований бюджет на обслуговування й хоче обрати якомога більше нафтопроводів для обслуговування, не перевищуючи бюджет. Однак країна повинна зберегти повноцінне функціонування своєї системи розподілу нафти — після виведення обраних нафтопроводів з ладу мережа повинна залишатися з'єднаною, щоб можна було транспортувати нафту між будь-якою парою вузлів.
Для кожного нафтопроводу відома вартість, необхідна для його виведення з ладу для технічного обслуговування. Допоможіть інженерам визначити, які нафтопроводи можна тимчасово вивести з ладу для технічного обслуговування, щоб максимізувати їхню кількість, дотримуючись бюджетного обмеження, при цьому залишивши мережу повністю з'єднаною.
У першому рядку задано кількість вузлів , кількість нафтопроводів та доступний бюджет на обслуговування (2 \le n \le 50000, 1 \le m \le 10^5, 0 \le s \le 10^{18}).
У наступних рядках міститься інформація про нафтопроводи — для кожного вказано, які два вузли він з'єднує, а також вартість його обслуговування (вартість не перевищує 10^9).
Нафту можна транспортувати кожним нафтопроводом у обох напрямках, і кожна пара вузлів з'єднана не більше ніж одним нафтопроводом.
У першому рядку виведіть максимальну кількість нафтопроводів, які інженери можуть тимчасово вивести з ладу для обслуговування. У другому рядку виведіть номери цих нафтопроводів (нумерація відповідає порядку у вхідних даних, починаючи з ).
Приклад 1