\includegraphics{https://static.e-olymp.com/content/2b/2ba4c21198a2c73f70fbd6f65dce371bfaf3e2ad.jpg} Одного разу Крош знову взяв страшну щелепу та й почав з нею бігати по лісі, лякаючи всіх підряд. Цього разу всі настільки злякались, що почали метушливо і хаотично бігати, стикаючись один з одним та витоптуючи грядки Копатича, попередньо знищивши огорожу Копатича, яка була гарненько зведена навколо грядки. І лише один практичний Їжачок не злякався, а подумав, що якщо таке буде продовжуватись регулярно, то дуже швидко ліс перетвориться в степ, а потім і в пустелю. Не буде ні грядок Копатича, ні дерева Совуньї... Щоб запобігти хаосу і всесвітній катастрофі, Їжачок вирішив не сидіти вдома склавши голки, а діяти. За його геніальним Планом Спасіння Світу (скорочено ПСС), необхідною і достатньою умовою було встановлення світлофорів посередині всіх доріг лісу, що змусило б Кроша та лякливих лісових жителів бігати не метушливо і хаотично, а у суворій відповідності з Правилами Дорожнього Руху (скорочено ПДР). Для реалізації цього хитромудрого плану, Їжачок попросив Піна зібрати і встановити світлофори на всіх серединах вулиць, пообіцявши йому за це дістати ліцензійний дистрибутив Microsoft Windows Vista. Почувши це, Пін страшно розлютився. І дійсно, пропонувати ЙОМУ, особисто зайомому з Tux'ом ТАКЕ?! Але занятись Піну було все одно нічим, і тому він все ж допоміг Їжачку. Правда для того, щоб наступного разу Їжачок пропонував йому нормальний софт, він встановив всього лише демо-версію світлофорів <<Lights 0.9.6 pre5 try7 beta3 build 4559>>, у яких був відсутній жовтий колір. Також, щоб все стало веселіше, Пін присвоїв кожному світлофору свій період перемикання. Побачивши все це, Крош вирішив <<пояснити>> Їжачку, що він був не правий, причому він захотів це зробити якомога щвидше. Попередньо для цього <<пояснення>> він приготував при допомозі щелепи максимально страшний вигляд, якого злякався навіть сам Крош, коли побачив його у дзеркалі. Щоб дістатись до Їжачка, Крош підібрав момент, коли всі світлофори одночасно увімкнулись і вже вирішив бігти, але тут зрозумів, що бігти-то можно різними шляхами, а хочеться добігти якомога швидше. По цій причині він попросив вас написати програмку, яка визначить мінімальний час, за який він зможе дістатись до Їжачка. Сам шлях Крошу не потрібний -- знаючи ліс, він легко визначить, куда бігти, якщо знає час. У початковий момент часу Крош знаходиться на перехресті з номером \textbf{1}. Будинок Їжачка розміщений біля перехрестя з номером \textbf{N} . \InputFile У першому рядку через пропуск записані цілі числа \textbf{N}, \textbf{M} та дійсне число \textbf{V}, де \textbf{N} -- кількість перехресть, \textbf{M} - кількість доріг, \textbf{V} -- швидкість руху Кроша ( \textbf{N} ≤ \textbf{100}, \textbf{M} < \textbf{10000}, \textbf{0} < \textbf{V} ≤ \textbf{100}). У кожному з наступних рядків знаходиться опис доріг у вигляді чотирьох чисел -- \textbf{A}, \textbf{B}, \textbf{L}, \textbf{P}, де \textbf{A} - початкове, \textbf{B} - кінцеве перехрестя (\textbf{A}, \textbf{B} ≤ \textbf{N}), \textbf{L} - довжина дороги, \textbf{P} -- період перемикання світлофора у середині даної дороги (\textbf{L},\textbf{P} ≤ \textbf{100}). Врахуйте, що числа \textbf{L} та \textbf{P} можуть бути дробовими. Два перехрестя може з'єднувати лише одна дорога. \OutputFile Вивести єдине дійсне число з двома знаками після коми -- мінімальний час в секундах, за який Крош зможе дістатись до Їжачка.