Світлофори - 2
Одного разу Крош знову взяв страшну щелепу та й почав з нею бігати по лісі, лякаючи всіх підряд. Цього разу всі настільки злякались, що почали метушливо і хаотично бігати, стикаючись один з одним та витоптуючи грядки Копатича, попередньо знищивши огорожу Копатича, яка була гарненько зведена навколо грядки.
І лише один практичний Їжачок не злякався, а подумав, що якщо таке буде продовжуватись регулярно, то дуже швидко ліс перетвориться в степ, а потім і в пустелю. Не буде ні грядок Копатича, ні дерева Совуньї... Щоб запобігти хаосу і всесвітній катастрофі, Їжачок вирішив не сидіти вдома склавши голки, а діяти. За його геніальним Планом Спасіння Світу (скорочено ПСС), необхідною і достатньою умовою було встановлення світлофорів посередині всіх доріг лісу, що змусило б Кроша та лякливих лісових жителів бігати не метушливо і хаотично, а у суворій відповідності з Правилами Дорожнього Руху (скорочено ПДР).
Для реалізації цього хитромудрого плану, Їжачок попросив Піна зібрати і встановити світлофори на всіх серединах вулиць, пообіцявши йому за це дістати ліцензійний дистрибутив Microsoft Windows Vista. Почувши це, Пін страшно розлютився. І дійсно, пропонувати ЙОМУ, особисто зайомому з Tux'ом ТАКЕ?! Але занятись Піну було все одно нічим, і тому він все ж допоміг Їжачку. Правда для того, щоб наступного разу Їжачок пропонував йому нормальний софт, він встановив всього лише демо-версію світлофорів «Lights 0.9.6 pre5 try7 beta3 build 4559», у яких був відсутній жовтий колір. Також, щоб все стало веселіше, Пін присвоїв кожному світлофору свій період перемикання.
Побачивши все це, Крош вирішив «пояснити» Їжачку, що він був не правий, причому він захотів це зробити якомога щвидше. Попередньо для цього «пояснення» він приготував при допомозі щелепи максимально страшний вигляд, якого злякався навіть сам Крош, коли побачив його у дзеркалі. Щоб дістатись до Їжачка, Крош підібрав момент, коли всі світлофори одночасно увімкнулись і вже вирішив бігти, але тут зрозумів, що бігти-то можно різними шляхами, а хочеться добігти якомога швидше. По цій причині він попросив вас написати програмку, яка визначить мінімальний час, за який він зможе дістатись до Їжачка. Сам шлях Крошу не потрібний – знаючи ліс, він легко визначить, куда бігти, якщо знає час. У початковий момент часу Крош знаходиться на перехресті з номером 1. Будинок Їжачка розміщений біля перехрестя з номером N
.
Вхідні дані
У першому рядку через пропуск записані цілі числа N, M та дійсне число V, де N – кількість перехресть, M - кількість доріг, V – швидкість руху Кроша ( N ≤ 100, M < 10000, 0 < V ≤ 100). У кожному з наступних рядків знаходиться опис доріг у вигляді чотирьох чисел – A, B, L, P, де A - початкове, B - кінцеве перехрестя (A, B ≤ N), L - довжина дороги, P – період перемикання світлофора у середині даної дороги (L,P ≤ 100). Врахуйте, що числа L та P можуть бути дробовими. Два перехрестя може з'єднувати лише одна дорога.
Вихідні дані
Вивести єдине дійсне число з двома знаками після коми – мінімальний час в секундах, за який Крош зможе дістатись до Їжачка.