Стрибати!#2366
Тигр обожнює стрибати! Проте стрибати лісом — не дуже зручно: то яма трапиться, то в дерево вріжешся. Розумний і добрий Кролик вирішив допомогти Тигру і побудувати кілька зручних доріг із жовтої цегли (адже жовтий — улюблений колір Тигра). Для цього Кролик склав повну карту Стоакрового лісу й визначив, які дороги можна прокласти і скільки цегли потрібно для кожної з них. Підрахувавши запаси цегли, Кролик зрозумів, що замість деяких доріг можна зробити справжні лісові магістралі — широкі дороги, якими Тигр зможе ще швидше бігати і ще більше насолоджуватися рухом. Щоб побудувати магістраль замість звичайної дороги, потрібно у разів більше цегли—незалежно від місцезнаходження дороги.
Кожна дорога з'єднує два цікаві для Тигра місця — домівки лісових мешканців, галявини для стрибків тощо. Кролик пронумерував цікаві місця цілими числами від до і перелічив можливі дороги. Тепер він хоче побудувати таку мережу доріг, щоб кількість магістралей була максимальною, але при цьому з будь-якого цікавого місця можна було потрапити в будь-яке інше. Для цього плану у Кролика є цеглин. Допоможи йому спланувати будівництво!
У першому рядку вхідних даних задано чотири цілі числа , , , (1 \leq n, m \leq 100000; 1 \leq k \leq 10^9; 1 \leq c \leq 1000) — кількість цікавих місць, кількість можливих доріг, загальна кількість наявної цегли та у скільки разів більше цегли потрібно для будівництва магістралі відповідно.
Кожен з наступних рядків описує дорогу трьома цілими числами a_i, b_i, l_i (1 \leq a_i, b_i \leq n; 1 \leq l_i \leq 10^6) — номери цікавих місць, які з'єднує ця дорога, та кількість цегли, необхідну для її будівництва.
Кожна дорога з'єднує два різних цікавих місця. Між одними і тими ж місцями може бути кілька різних доріг.
Якщо побудувати таку мережу доріг неможливо, виведи одне слово Impossible.
Інакше виведи у першому рядку два цілі числа та — кількість звичайних доріг і магістралей в оптимальному плані відповідно. У другому рядку виведи цілих чисел — номери звичайних доріг, які буде побудовано, у зростаючому порядку. У третьому рядку виведи цілих чисел — номери магістралей також у зростаючому порядку.
Номери доріг відповідають їхній черзі у вхідних даних. Якщо існує кілька оптимальних рішень, виводи будь-яке з них.
Приклад 1