Как-то раз Крош снова взял страшную челюсть и стал с ней бегать по лесу, пугая всех в округе. В этот раз все настолько испугались, что стали лихорадочно и беспорядочно бегать, сталкиваясь друг с другом и вытаптывая грядки Копатыча, предварительно снеся забор Копатыча, любовно выстроенный вокруг грядок.

И один лишь практичный Ежик не испугался, а подумал, что если такое будет продолжаться регулярно, то скоро лес превратится в степь, а затем в пустыню. Не будет ни грядок Копатыча, ни дерева Совуньи... Чтобы предотвратить хаос и вселенскую катастрофу, Ежик решил не сидеть дома сложа иголки, а действовать. По его гениальному Плану Спасения Мира (сокращенно ПСМ), необходимым и достаточным условием было установление светофоров посередине всех дорог леса, что заставило бы Кроша и пугливых лесных обитателей бегать не лихорадочно и хаотично, а в строгом соответствии с Правилами Дорожного Движения (сокращенно ПДД).

Для реализации этого хитроумного плана, Ежик попросил Пина собрать и установить светофоры на всех серединах улиц, пообещав ему за это достать лицензионный дистрибутив 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 могут быть дробными. Два перекрёстка может соединять только одна дорога.

Выходные данные

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