Tullan!
Tiqr tullanmağı sevir! Təəssüf ki, meşədə tullana-tullana getmək çox rahat deyil - həm çuxura ilişmək, həm də ağaca çırpılmaq olar. Ağıllı və yaxşı Dovşan Tiqra kömək etmək qərarına gəldi və sarı kərpicdən bir neçə rahat yol tikmək istədi (axı sarı Tiqrun sevimli rəngidir). Bunun üçün o, Yüzakrlıq Meşəsinin tam xəritəsini hazırladı və hansı yolların tikilə biləcəyini və hər birinə nə qədər kərpic lazım olduğunu hesabladı. Kərpic ehtiyatlarını qiymətləndirərək, Dovşan başa düşdü ki, bəzi yollar əvəzinə əsl meşə avtomagistralları tikmək olar - geniş yollar ki, Tiqr daha sürətli qaça bilsin və hərəkətdən daha çox zövq alsın. Avtomagistral tikmək üçün adi yol əvəzinə c dəfə çox kərpic lazımdır, yolun yerləşməsindən asılı olmayaraq.
Hər bir yol Tiqr üçün maraqlı olan iki yeri birləşdirir - Meşə sakinlərinin evləri, o tullana biləcəyi çəmənliklər və s. Dovşan maraqlı yerləri 1-dən n-ə qədər tam ədədlərlə nömrələdi və mümkün yolların siyahısını yazdı. İndi o, yol şəbəkəsini elə qurmaq istəyir ki, mümkün qədər çox avtomagistral tikilsin, lakin hər bir maraqlı yerdən istənilən digərinə keçmək mümkün olsun. Bu planı həyata keçirmək üçün Dovşanın k kərpici var. Ona yolların tikintisini planlaşdırmağa kömək edin!
Giriş verilənləri
Giriş faylının ilk sətiri dörd tam ədəd n, m, k və c (1 ≤ n, m ≤ 100000; 1 ≤ k ≤ 10^9; 1 ≤ c ≤ 1000) - maraqlı yerlərin sayı, mümkün yollar, ümumi kərpic sayı və avtomagistral tikmək üçün neçə dəfə çox kərpic lazım olduğunu göstərir.
Növbəti m sətir yolların təsvirini ehtiva edir - üç tam ədəd a_i, b_i, l_i (1 ≤ a_i, b_i ≤ n; 1 ≤ l_i ≤ 10^6) - yolun birləşdirdiyi maraqlı yerlərin nömrələri və bu yolun tikintisi üçün lazım olan kərpic miqdarı.
Hər bir yol iki fərqli maraqlı yeri birləşdirir. İki maraqlı yer arasında bir neçə yol ola bilər.
Çıxış verilənləri
Əgər belə bir yol şəbəkəsi qurmaq mümkün deyilsə, çıxış faylına yalnız "Impossible" sözünü yazın.
Əks halda, çıxış faylının birinci sətirində optimal planda adi yolların və avtomagistralların sayını göstərən iki tam ədəd p və q yazın. İkinci sətirdə p tam ədəd - tikilməli olan adi yolların nömrələrini artan sırada yazın. Üçüncü sətirdə q tam ədəd - avtomagistralların nömrələrini də artan sırada yazın.
Yollar giriş faylında göründüyü sırayla nömrələnib. Bir neçə optimal həll varsa, istənilənini çıxış edin.