Ad günün mübarək#2852
Çoxdan gözlənilən ad günü gəlib çatıb. Yalnız bir sınaq qalıb: İranın evinə çatmaq.
Şəhərdə ən populyar nəqliyyat vasitəsi marşrutkadır. Hər bir marşrutkanın iki sürücüsü var: biri bir marşrutu, digəri başqa bir marşrutu üstün tutur. Lakin hər iki sürücü üçün başlanğıc dayanacağı və yola düşmə vaxtı eynidir. Hər gün sürücülərdən biri işləyir, digəri istirahət edir. Əgər Saşa istənilən dayanacaqda olarsa, həmin dayanacaqdan çıxan marşrutkalarda bu gün hansı sürücülərin işlədiyini dərhal öyrənir. Lakin dayanacağa çatmamışdan əvvəl yalnız marşrutkaların mümkün hərəkət cədvəlini və birinci sürücünün bu gün işləməsi ehtimalını bilir. Saşa dayanacaq 1-in yaxınlığında yaşayır və orada istənilən vaxt ola bilər, İra isə dayanacaq N-in yaxınlığında yaşayır. Saşanın ad günündə İraya çatmaq üçün gözlənilən çatma vaxtını tapmalısınız. Saşa heç vaxt İraya çatmama ehtimalı olan marşrutu seçməyəcək və digər bütün mümkün marşrutlar arasında gözlənilən çatma vaxtını minimallaşdıran marşrutu seçəcək.
Vacib faktlar:
Marşrutka şəbəkəsi dövrəsiz istiqamətli qrafdır.
Marşrutkalar arasında keçid ani baş verir.
Optimal strategiyanı müəyyənləşdirərkən Saşa nəzərə alır ki, hər bir dayanacağa çatanda həmin gün hansı sürücülərin işlədiyini öyrənəcək.
İlkin olaraq, Saşa başlanğıc dayanacağındakı sürücüləri də bilmir.
Birinci sətirdə iki tam ədəd və (2 \leq N \leq 10^5, 0 \leq K \leq 10^5) — dayanacaq və işlək marşrutkaların sayı verilir. Sonrakı sətirin hər birində bir marşrutka haqqında yeddi tam ədəd: v_1 a_1 v_2 a_2 (1 \leq u, v_1, v_2 \leq N, u \neq v_1, u \neq v_2, 0 \leq d, a_1, a_2 \leq 1440, d < a_1, d < a_2, 0 < p < 100) — dayanacağın nömrəsi və yola düşmə vaxtı, birinci sürücünün işləməsi ehtimalı, həmçinin hər sürücü üçün: təyinat dayanacağı və çatma vaxtı verilir.
Bir ədəd çıxarın — -ci dayanacağa çatmaq üçün gözlənilən vaxtın qiymətini 10^{-6} dəqiqliklə və ya ondan daha kiçik mütləq və ya nisbi xətayla çıxarın, yaxud ora çatmamaq ehtimalı sıfırdan böyükdürsə, çıxarın.
Nümunə 1