Marşrut Dəyişikliyi
Yol sistemi bir ölkənin bütün N şəhərlərini birləşdirir və mövcud yollarla istənilən iki şəhər arasında səyahət mümkündür. Hər bir yol iki fərqli şəhəri birləşdirir, iki tərəflidir və hər birində dəqiq bir ödəniş məntəqəsi var (hər iki istiqamətdə ödəniş edilir). Yollar yalnız bir şəhərdə kəsişir və heç bir şəhər cütü iki və ya daha çox yolla bir-birinə bağlı deyil.
Dias Transport şəhərlər arasında bir günlük bağlama çatdırma xidməti təklif edir. Hər bir bağlama şəhər A-dan başqa bir şəhər B-yə daşınmalıdır. Dias Transport rəhbərliyi hər bir bağlama üçün C şəhərdən və C-1 yoldan ibarət xidmət marşrutu təyin edir: xidmət marşrutunun ilk şəhəri bağlamanın mənşəyi, son şəhəri isə bağlamanın təyinatıdır. Xidmət marşrutu heç vaxt eyni şəhərdən iki dəfə keçmir və bağlamanı çatdırmaq üçün seçilən nəqliyyat vasitəsi yalnız təyin olunmuş xidmət marşrutu ilə hərəkət edə bilər.
Bir gün, lakin, bir nəqliyyat vasitəsi sıradan çıxdı və xidmət marşrutunda olmayan bir şəhərdə təmirə aparıldı. Dias Transport rəhbərliyi bağlamanı çatdırmaq üçün ən aşağı ümumi ödəniş xərclərini (yəni, nəqliyyat vasitəsini təmir edildiyi şəhərdən təyinat şəhərinə aparmaq üçün) bilmək istəyir, lakin əlavə bir məhdudiyyətlə: əgər nəqliyyat vasitəsi bir anda xidmət marşrutunu təşkil edən şəhərlərdən birinə çatarsa, xidmət marşrutunu izləməyə geri dönməlidir.
Giriş verilənləri
Giriş bir neçə test halını ehtiva edir.
Bir test halının ilk sətri dörd tam ədəd N, M, C və K (4 ≤ N ≤ 250, 3 ≤ M ≤ N×(N-1)/2, 2 ≤ C ≤ N-1 və C ≤ K ≤ N-1) ehtiva edir, müvafiq olaraq, şəhərlərin sayı, yolların sayı, xidmət marşrutundakı şəhərlərin sayı və nəqliyyat vasitəsinin təmirə aparıldığı şəhər. Şəhərlər 0-dan N-1-ə qədər tam ədədlərlə müəyyən edilir. Xidmət marşrutu 0, 1, ..., C-1 şəklindədir, yəni mənşə 0-dır, 0-dan 1-ə, 1-dən 2-yə və s. gedir, təyinat isə C-1-dir. Növbəti M sətir yol sistemini təsvir edir. Bu sətirlərin hər biri bir yolu təsvir edir və üç tam ədəd U, V və P (0 ≤ U, V ≤ N-1, U ≠ V, 0 ≤ P ≤ 250) ehtiva edir, bu da şəhərlər U və V arasında P dəyərində ödəniş olan bir yolun olduğunu göstərir.
Son test halı boşluqlarla ayrılmış dörd sıfırdan ibarət bir sətirlə tamamlanır.
Çıxış verilənləri
Hər bir test halı üçün proqramınız bir sətir çap etməlidir, bu sətir nəqliyyat vasitəsinin təyinat şəhərinə çatması üçün minimum ümumi ödəniş xərci olan tək bir tam ədəd olmalıdır.