\includegraphics{https://static.e-olymp.com/content/2b/2ba4c21198a2c73f70fbd6f65dce371bfaf3e2ad.jpg} Bir dəfə Kroşa yenidən qorxulu çənəni götürərək onunla bütün ətrafdakıları qorxuzmaqla meşədə qaçırdı. Bu dəfə hamı o qədər qorxmuşdu ki, bir-biri ilə toqquşur və Kopatıçın əvvəlcə ləklərin ətrafına həvəslə çəkdiyi hasarı uçuraraq, Kopatıçın ləklərini tapdalayaraq qaçmaq həyəcanlı və nizamsız idi. Və yalnız təcrübəli Kirpi qorxmadı, amma düşündü ki, müntəzəm olaraq belə davam edərsə, onda tezliklə meşə çöllüyə, sonra isə səhraya çevriləcək. Nə Kopatıçın ləkləri , nə də Sovunun ağacları olmayacaq... Xaos və ümumdünya fəlakətinin qarşısını almaq üçün Kirpi evdə iynə üstdə oturmamağı, fəaliyyət göstərməyi qərara aldı. Onun Dünyanı Xilas Etməyin Baş Planınına (qısaca DXEBP) əsasən Kroşa və qorxan meşə sakinlərinin həyəcanla və xaotik qaçmaması və Yol Hərəkəti Qaydalarına (qısaldılmış YHQ) ciddi riayət etməsi üçün zəruri və kafi şərt bütün meşə yollarının ortasında sfetoforların qurulması idi. Bu hiyləgər planın reallaşdırılması üçün Kirpi Pinadan bütün yolların ortasına sfetoforların yığılıb quraşdırılmasını xahiş etdi və bunun əvəzində ona Microsoft Windows Vista distributunun lisenziyasını almağı vəd etdi. Bunu eşidən Pina dəhşətli dərəcədə hirsləndi. Əslində, Ona, şəxsən Köhnələri bilənə belə təklif etmək?! Lakin Pinanın heç bir vacib işi yox idi, ona görə də hər halda Kirpiyə kömək etdi. Doğrudur, gələcəkdə Kirpinin ona normal proqram təminatı təklif etməsi üçün o, svetoforlara sarı işıq olmayan <<Lights 0.9.6 pre5 try7 beta3 build 4559>> demo-versiyasını quraşdırdı. Həmçinin, bütün bunların darıxdırıcı olmaması üçün Pin hər svetofora öz dəyişmə periodunu verdi. Bütün bunları görən Kroş Kirpiyə “anlatmaq” istədi ki, bu doğru deyil, belə ki, o istəyirdi ki, bunu mümkün qədər tez etsin. Bunu anlatmaq üçün o, əvvəlcədən bir çənənin vasitəsi ilə hətta onu güzgüdə görəndə Kroşun qorxa biləcəyi bir sifət düzəltdi. Kirpiyə yetişmək üçün Kpoş elə moment seçdi ki, bütün svetoforlar eyni vaxtda işə düşsün və artıq qaçmağı qərara aldıqda anladı ki, müxtəlif yollarla da qaçmaq olarmış, amma mümkün qədər tez çatmaq istəyir. Buna görə də o, sizdən Kirpiyə çata biləcəyi ən az vaxtı müəyyənləşdirən proqramı tərtib etməyi xahiş edir. Yolun özü Kpoşa lazım deyil, meşəni tanıdığına görə vaxtı bilirsə, haraya qaçmağı o asanlıqla müəyyənləşdirə bilir. Başlanğıc anda Kpoş\textbf{ 1} nömrəli kəsişmədə yerləşir. Kirpinin evciyi isə\textbf{ N} nömrəli kəsişmənin yanında yerləşir. \InputFile Birinci sətirdə aralarında boşluq işarəsi olmaqla tam\textbf{ M} və \textbf{N} və həqiqi \textbf{V} ədədləri yazılır. Burada,\textbf{ N} kəsişmələrin sayı, \textbf{M} yolların sayı\textbf{, V} Kroşanın hərəkət sürətidir( \textbf{N} ≤ \textbf{100}, \textbf{M} <\textbf{10000}, \textbf{0} < \textbf{V} ≤ \textbf{100}). Sonrakı hər bir sətirdə yolların təsviri dörd \textbf{A}, \textbf{B}, \textbf{L}, \textbf{P} ədədləri ilə verilir. Burada, \textbf{A} başlanğıc, \textbf{B }sonuncu kəsişmələrdir (\textbf{A}, \textbf{B} ≤ \textbf{N}), \textbf{L} yolun uzunluğu, \textbf{P} isə verilmiş yolun ortasındakı svetoforun dəyişmə periodudur (\textbf{L},\textbf{P} ≤ \textbf{100}). Nəzərə alın ki, \textbf{L} və \textbf{P }ədədləri kəsr də ola bilər. İki kəsişmə yalnız bir yolu birləşdirə bilər. \OutputFile Vergüldən sağda iki rəqəm dəqiqliyi ilə yeganə bir həqiqi ədədi- Kroşun Kirpiyə çata biləcəyi ən az vaxtı saniyə ilə verin.