Avtomobil yürüşü
Antilop-Qnu marşrutu qonaqpərvər və səxavətli yerlərdən keçir. Bu marşrutda hər hansı bir şəhərə vacib bir teleqramın gəlməsi və ya Panvkovskinin köhnə işlərinə qayıtması ehtimalı var ki, bu da həmin şəhərdə 24 saatlıq bir gecikməyə səbəb ola bilər. Beləliklə, marşrutun keçid vaxtı sabit deyil və təsadüfi dəyişə bilər. Leytenant Şmidt uşaqları Çernomorsk şəhərinə mümkün qədər tez çatdırmalıdır, yüz faiz olmasa da, müəyyən edilmiş ehtimaldan az olmayan bir ehtimalla. Marşrutdakı hər bir şəhərdə gecikmə ehtimalları eynidir və bu gecikmələr bir-birindən asılı deyil. Marşrutun müddətini elə bir T sayı ilə ifadə edək ki, marşrutu T vaxtından çox olmayan bir müddətdə keçmə ehtimalı verilmiş ehtimal P-dən az olmasın. Marşrutun keçidi zamanı ilk və son şəhərdə mümkün gecikmə nəzərə alınır.
Onlara minimal müddətli marşrutu tapmağa kömək edin.
Giriş verilənləri
Birinci sətirdə iki tam ədəd N və M — şəhərlərin sayı və aralarındakı yolların sayı, və iki onluq ədəd P — marşrutun keçid vaxtının axtarıldığı verilmiş ehtimal və P_1 — hər bir şəhərdə 24 saatlıq gecikmə ehtimalı (2 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ P, P_1 ≤ 1). P və P_1 ondalık nöqtədən sonra beş rəqəmlə verilir.
Sonra M sətir gəlir — yolların təsvirləri, hər birində üç tam ədəd A_i, B_i, L_i — verilmiş yolla birləşdirilən şəhərlərin nömrələri və onun keçid vaxtı saatlarla (1 ≤ L_i ≤ 1000). Şəhərlər 1 -dən N-ə qədər nömrələnmişdir. Marşrut 1 nömrəli şəhərdən N nömrəli şəhərə çəkilir. Hər bir şəhər cütü bir yoldan çox birləşdirilməyib. Heç bir yol şəhəri özü ilə birləşdirmir. Yollarla hər iki istiqamətdə hərəkət etmək mümkündür. İstənilən iki şəhər arasında yolun mövcudluğu və P-nin 10^{–9}-dan çox olmayan bir dəyişməsi ilə istənilən marşrutun müddətinin dəyişməyəcəyi təmin edilir.
Çıxış verilənləri
Çıxış faylının birinci sətirində bir tam ədəd — optimal marşrutun keçdiyi şəhərlərin sayı verilməlidir. İkinci sətirdə bu şəhərlərin nömrələri ardıcıllıqla boşluqla ayrılaraq verilməlidir.