Tullan!#2366
Pələng hoppanmağı çox həvəslidir! Lakin meşədə hoppanmaq o qədər də rahat deyil — yolda cığıllar və ağaclar mane olur. Zəki və mehriban Dovşan Pələngə kömək etmək üçün bir neçə rahat yol tikməyə qərar verdi; yollar Pələngin sevimli rəngi olan sarı kərpiclərdən tikiləcək. Bunun üçün Dovşan "Yüz Akrlıq Meşə"nin tam xəritəsini tərtib etdi və hansı yolların tikilə biləcəyini, hər bir yol üçün neçə kərpic lazım olduğunu hesabladı. Kərpic ehtiyatlarını nəzərdən keçirib Dovşan başa düşdü ki, bəzi yollar əvəzinə həqiqi meşə magistralları da tikmək mümkündür — Pələngin daha sürətli qaça və daha çox zövq ala biləcəyi enli yollar! Magistral yolun tikilməsi üçün yerləşməsindən asılı olmayaraq, adi yolla müqayisədə c dəfə çox kərpic lazımdır.
Hər yol Pələng üçün maraqlı olan iki yeri — meşə sakinlərinin evlərini, hoppanmaq üçün meydançaları və s. — birləşdirir. Dovşan maraqlı yerləri -dən -ə qədər ədədlərlə nömrələdi və mümkün yolları qeyd etdi. İndi o istəyir ki, elə yol şəbəkəsi tiksin ki, magistralların sayı maksimum olsun, lakin hələ də istənilən maraqlı yerdən digərinə getmək mümkün olsun. Bu plan üçün Dovşanın kərpici var. Ona yol quruluşunu planlaşdırmaqda kömək et!
Girişin birinci sətrində dörd tam ədəd , , , və (1 \leq n, m \leq 100000; 1 \leq k \leq 10^9; 1 \leq c \leq 1000) — maraqlı yerlərin sayı, mümkün yolların sayı, mövcud kərpiclərin cəmi, və magistral yol üçün lazım olan kərpicin adi yolla müqayisədə neçə dəfə artıq olduğu verilir.
Növbəti sətrin hər birində yol haqqında üç tam ədəd a_i, b_i, l_i (1 \leq a_i, b_i \leq n; 1 \leq l_i \leq 10^6) — yolun birləşdirdiyi maraqlı yerlərin nömrələri və bu yolun tikilməsi üçün lazım olan kərpiclərin sayı verilir.
Hər bir yol iki fərqli maraqlı yeri birləşdirir. İki maraqlı yer arasında bir neçə fərqli yol ola bilər.
Əgər belə yol şəbəkəsini qurmaq mümkün deyilsə, bircə söz yazın: **Impossible**.
Əks halda, birinci sətirdə iki tam ədəd və — optimal plan üzrə tikiləcək adi yolların və magistralların sayı verin. İkinci sətirdə ədədi artan sıra ilə — tikiləcək adi yolların nömrələrini yazın. Üçüncü sətirdə ədədi artan sıra ilə — tikiləcək magistralların nömrələrini yazın.
Yollar girişdə verildiyi ardıcıllıqla nömrələnir. Əgər bir neçə optimal həll varsa, istənilən birini vermək olar.
Nümunə 1