Aviabiletlər#4456
Professor Ford beynəlxalq konfransa getməlidir və səyahət xərclərini minimuma endirmək istəyir. Otel xərclərinə qənaət etmək üçün yalnız gecə reysləri ilə səyahət etməyə və gündüzləri ötüb keçdiyi şəhərlərdə gəzintiyə çıxmağa qərar verir. O, uçuş cədvəllərini diqqətlə araşdırır və münasib gecə reyslərini seçir. Məlum olur ki, seçilən istiqamətlər üzrə reyslər hər gecə işləyir və o, bir gecədə bir dəfədən artıq uçuş edə bilməz.
Verilmişlər üzrə professorun konfransa çatması üçün minimum xərcli marşrutu tapmaq tələb olunur. Qeyd olunur ki, konfransadək gecə qalıb (yəni professor ən çox uçuş edə bilər).
Birinci sətirdə beş tam ədəd verilir: (şəhərlərin sayı), (uçuşların sayı), (qalan gecələrin sayı), (professorun yaşadığı şəhərin nömrəsi) və (konfransın keçiriləcəyi şəhərin nömrəsi). Məhdudiyyətlər: 2 \leq N \leq 100, 1 \leq M \leq 10^5, 1 \leq K \leq 100, 1 \leq S \leq N, 1 \leq F \leq N.
Növbəti sətrin hər birində üç tam ədəd verilir: S_i, F_i, P_i, burada S_i -ci uçuşun çıxış şəhəridir, F_i -ci uçuşun çatdığı şəhərdir və P_i -ci uçuşun qiymətidir. Məhdudiyyətlər: 1 \leq S_i \leq N, 1 \leq F_i \leq N, 1 \leq P_i \leq 10^6.
Bir ədəd çap edin — professor üçün münasib olan ən ucuz marşrutun minimal dəyəri. Əgər gecə ərzində konfrans şəhərinə çatmaq mümkün deyilsə, çap edin.
Nümunə 1