Körpülər#5372
Uzaq bir ölkədə, çayın deltası ərazisində ada var idi və hər adada bir şəhər yerləşirdi. Şəhərlər elə yollarla birləşmişdi ki, istənilən iki şəhər arasında yalnız bir marşrut mövcud idi (bəlkə də başqa şəhərlərdən keçməklə). Ancaq hər yol çayı keçərkən kəsişirdi, çünki körpülər hələ məlum deyildi və belə yollarla səyahət etmək qeyri-rahat idi, yalnız atla mümkündür.
Körpü tikmə texnologiyası ortaya çıxdıqdan sonra, kral bəzi keçidləri körpülərlə əvəz etmək qərarına gəldi ki, yolları daha rahat hala gətirsin. Körpülər çayı hətta karvanlarla keçməyə imkan verirdi. Krala bu ideya çox xoş gəldi və mümkün qədər çox körpü tikməyi əmr etdi. Ancaq ölkə kasıb idi, buna görə yalnız körpü tikmək mümkün idi.
Kral sizə, baş məsləhətçisinə, bir tikinti planı hazırlamağa müraciət etdi. Siz keçidi elə seçməlisiniz ki, bütün şəhər cütləri arasındakı ümumi səyahət vaxtı minimal olsun. Fərz edin ki, adi yollarda atla, körpü olan yollarda isə karvanla səyahət edirlər.
Birinci sətir dörd tam ədədi əhatə edir: n, k~(1 \le k < n \le 10000), s_h və s_c~(1 \le s_h, s_c \le 10^5) — şəhərlərin sayı, tikiləcək körpü sayı, atın sürəti və karvanın sürəti (metr / saniyə).
Daha sonra gələn hər bir n - 1 sətir üç tam ədəd ehtiva edir: b_i, e_i — yol ilə birləşdirilən şəhərlər və l_i~(1 \le l_i \le 10^6) — yolun uzunluğu metrlə.
Şəhərlər -dən -ə qədər nömrələnir, yollar isə -dən n - 1-ə qədərdir.
ədəd çıxarın — körpülərin tikilməli olduğu yolların nömrələri. Əgər bir neçə optimal variant varsa, hər hansı birini çap edə bilərsiniz.