\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 Вывести единственное вещественное число с двумя знаками после запятой -- минимальное время в секундах, за которое Крош сможет добраться до Ежика.