Daşınma
"Yandex" şirkəti bütün məktəblilərə və LKS müəllimlərinə xüsusi fincanlar hədiyyə etmək qərarına gəlib. Lakin tələb olunan fincanların sayı o qədər çoxdur ki, istehsalçı onları Yandex ofisinə son anda çatdırıb. Fincanları Moskvadan "Berendeyev polyanı"na çatdırmaq üçün cəmi 24 saat vaxt qalıb.
Sifariş verilən fincanların sayı 10^7 (təşkilatçılar məhz bu qədər sifariş veriblər), və təbii ki, bu qədər fincanı bir reysdə çatdırmaq mümkün deyil. Amma ilk reysdə mümkün qədər çox fincan çatdırmaq istəyirlər. Daşınma üçün bir böyük yük maşını sifariş edilib. Lakin bəzi yollarda avtomobilin çəkisinə məhdudiyyət qoyulub. Buna görə də, avtomobili fincanlarla tam yükləsəniz, bəlkə də ən qısa marşrutdan istifadə etmək mümkün olmayacaq və dolanbac yolla getmək lazım gələcək. Hətta elə ola bilər ki, bu səbəbdən yük maşını düşərgəyə vaxtında çatdırılmayacaq və buna heç cür yol vermək olmaz.
Beləliklə, bu qiymətli yükü vaxtında çatdırmaq və yol hərəkəti qaydalarını pozmamaq üçün avtomobilə neçə fincan yükləmək olar?
Giriş verilənləri
Birinci sətirdə n (1 ≤ n ≤ 500) və m - yol sxeminin düyün nöqtələrinin və yolların sayı verilir. Növbəti m sətirdə yollar haqqında məlumat verilir. Hər bir yol ayrıca sətirdə aşağıdakı kimi təsvir edilir. Əvvəlcə bu yolun birləşdirdiyi düyün nöqtələrinin nömrələri, sonra bu yolda keçən vaxt və nəhayət, bu yolla getməyə icazə verilən avtomobilin maksimum çəkisi göstərilir. Bütün yollar müxtəlif nöqtələri birləşdirir və hər bir nöqtə cütü üçün onları birbaşa birləşdirən ən çox bir yol var. Bütün rəqəmlər bir və ya bir neçə boşluqla ayrılır.
Düyün nöqtələri 1-dən n-ə qədər nömrələnib. Bu zaman "Yandex" ofisi 1 nömrəli, "Berendeyev polyanı" isə n nömrəli nöqtəyə malikdir. Yolun keçmə vaxtı dəqiqələrlə verilir və 1440 (24 saat) dəqiqəni keçmir. Çəki məhdudiyyəti qramla verilir və bir milyardı keçmir. Bundan əlavə, bir fincan 100 qram, boş yük maşını isə 3 ton ağırlığındadır.
Çıxış verilənləri
Bir rəqəm çıxarın - ilk reysdə 24 saatdan çox vaxt sərf etmədən gətirilə biləcək maksimum fincan sayı.