Ad günün mübarək
Gözlənilən ad günü gəldi və yalnız bir sınaq qaldı — İrin evinə çatmaq.
Şəhərdə ən populyar nəqliyyat növü marşrutlardır. Hər marşrutun iki sürücüsü var; biri bir marşrutu, digəri isə başqa bir marşrutu sevir. Lakin, hər iki sürücü üçün marşrutların yola düşmə yeri və vaxtı eynidir. Hər gün sürücülərdən biri işləyir, digəri isə istirahət edir. Saşa hansısa dayanacaqda olduqda, dərhal həmin dayanacaqdan yola düşən marşrutlarda bu gün hansı sürücülərin işlədiyini öyrənir. Lakin dayanacağa çatana qədər o, yalnız marşrutların mümkün hərəkət cədvəlini və birinci sürücünün işləmə ehtimalını bilir. Saşa dayanacaq 1-in yaxınlığında yaşayır və istənilən vaxt orada ola bilər, İra isə dayanacaq N-in yaxınlığında yaşayır. Saşanın ad günündə İraya çatma vaxtının riyazi gözləntisini tapmaq lazımdır. Bu zaman Saşa heç vaxt İraya ümumiyyətlə çatmamağa səbəb ola biləcək bir üsuldan istifadə etməyəcək və digər bütün üsullar arasında çatma vaxtını minimallaşdıran üsulu seçəcək.
Vacib faktlar:
Marşrutların hərəkət şəbəkəsi dövrsüz istiqamətli qrafdır.
Marşrutdan marşruta keçid dərhal baş verir.
Optimal strategiyanı müəyyən edərkən Saşa hər bir dayanacağa çatdıqda bu günkü sürücüləri öyrənməyi də nəzərə alır.
Saşa öz dayanacağı haqqında da əvvəlcə heç nə bilmir.
Giriş verilənləri
Birinci sətirdə iki ədəd N və K (2 ≤ N ≤ 10^5, 0 ≤ K ≤ 10^5) — dayanacaqların və aktiv marşrutların sayı verilir. Daha sonra hər bir K sətirdə marşrutlar haqqında məlumat verilir: yeddi tam ədəd u d p v_1 a_1 v_2 a_2 (1 ≤ u, v_1, v_2 ≤ N, u ≠ v_1, u ≠ v_2, 0 ≤ d, a_1, a_2 ≤ 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ə ehtimalı, birinci sürücü işləyirsə çatma yeri və vaxtı, ikinci sürücü işləyirsə çatma yeri və vaxtı.
Çıxış verilənləri
Yeganə ədəd — dayanacaq N-ə çatma vaxtının riyazi gözləntisi 10^{-6} dəqiqliklə və ya -1, əgər ora çatmamaq ehtimalı varsa.