Yeni səyahətin başlanğıcı
Gün gəldi, xanımlar və cənablar! Biz gəlin aparırıq! Lakin, həmişə olduğu kimi, Bakının dar yolları və uşaqlar maşınların yolunu kəsir və ənənəvi olaraq pul istəyirlər. Yazıq Rəşadın çox pulu yoxdur ki, uşaqlara xərcləsin! Həmçinin, o, mümkün qədər çox maşının onunla getməsini istəyir. O, çox düşündü və maksimum effektivliyə malik yolu seçməyə qərar verdi. Yolun effektivliyi, onunla gedə biləcəyi maksimum maşın sayının uşaqlara verməli olduğu ümumi xərcə bölünməsi ilə müəyyən edilir (effektivlik = maşın_sayı / ümumi_xərc). Yolun başlanğıcında, Rəşadın götürə biləcəyi maşınların sayı yolun bütün yollarının minimum eni ilə bərabərdir. Bizə Bakının mövcud yolları verilir, hər bir yolun eni və xərc var və iki məkanı birləşdirir, və sizdən 1 məntəqəsindən N məntəqəsinə gedən mümkün yolun maksimum effektivliyini tapmaq tələb olunur. Çıxış formatı üçün çıxış təfərrüatlarına baxın.
Giriş:
Birinci sətirdə N (1 ≤ N ≤ 10^3 ) və M (1 ≤ M ≤ 10^4 ) ədədləri verilir. Növbəti M sətirin hər biri yolun birinci son nöqtəsini, yolun ikinci son nöqtəsini, yolun xərcini x[i] (1 ≤ x[i] ≤ 10^3 ) və yolun enini y[i] (1 ≤ y[i] ≤ 10^3 ) ehtiva edir.
Çıxış:
Yolun maksimum effektivliyini 1000000 dəfə artırıb, aşağıya doğru yuvarlaqlaşdırılmış tam ədəd kimi çap edin.
Birinci test nümunəsi üçün izah
Bu nümunədə, 1-dən N-ə yalnız bir yol var. Eni min(3, 4)=3 və xərc 2+5=7. 3/7=0.428571428571..