Мости#5372
У далекій країні, розташованій у дельті ріки, було островів, і на кожному з них знаходилось місто. Міста були з'єднані дорогами так, що між будь-якою парою міст існував рівно один маршрут (можливо, проходячи через інші міста). Проте кожна дорога перетинала річку вбрід, оскільки мости ще не були відомі, і подорож такими шляхами була незручною та здійснювалась лише на конях.
Після того як з'явилася технологія будівництва мостів, король вирішив замінити деякі броди на мости, щоб зробити дороги більш зручними для пересування. Мости дозволяли перетинати річку навіть на каретах. Королю сподобалася ця ідея, і він наказав побудувати якомога більше мостів. Проте країна була бідною, тому можна було звести лише мостів.
Король звернувся до вас, свого головного радника, з проханням розробити план будівництва. Вам потрібно вибрати бродів таким чином, щоб загальний час подорожі між усіма парами міст став мінімальним. Вважайте, що по звичайних дорогах їздять на конях, а по дорогах з мостами — на каретах.
Перший рядок містить чотири цілі числа: n, k~(1 \le k < n \le 10000), s_h і s_c~(1 \le s_h, s_c \le 10^5) — кількість міст, кількість мостів, які потрібно побудувати, швидкість коня і швидкість карети (в метрах за секунду).
Кожний з наступних n - 1 рядків містить три цілі числа: b_i, e_i — міста, з'єднані дорогою, та l_i~(1 \le l_i \le 10^6) — довжина дороги в метрах.
Міста пронумеровані від до , дороги — від до n - 1.
Виведіть чисел — номери доріг, на яких мають бути побудовані мости. Якщо існує декілька оптимальних варіантів, ви можете вивести будь-який з них.