Neft müqaviləsi#5668
Neft çox mühüm strateji resursdur. Son zamanlar neftlə zəngin Qari ölkəsi öz neft nəqliyyat sistemini müasirləşdirmək və səmərəliliyini artırmaq qərarına gəlib. Sistem müxtəlif düyünləri — neft hasilatı məntəqələri, əsas ölkə şəhərləri və limanları birləşdirən boru kəmərlərindən ibarətdir. Boru kəmərləri şəbəkəsi elə layihələndirilib ki, istənilən düyündən istənilən başqa düyünə neftin nəqli mümkündür.
Sistemin etibarlılığını təmin etmək və mümkün dayanma müddətini minimuma endirmək üçün mühəndis komandasının müəyyən etdiyi bəzi boru kəmərləri müvəqqəti olaraq texniki xidmət və ya yenilənmə üçün sistemdən çıxarıla bilər. Hər bir boru kəməri müəyyən texniki xidmət xərci ilə müvəqqəti olaraq sökülə bilər. Mühəndis komandasının sabit bir texniki xidmət büdcəsi var və mümkün qədər çox boru kəmərini texniki xidmətə götürmək, lakin büdcəni aşmamaq istəyir. Bununla yanaşı, ölkə neft paylama sisteminin tam işləməyə davam etməsini tələb edir — seçilmiş boru kəmərləri texniki xidmətə çıxarıldıqdan sonra şəbəkə hələ də bütövlüklə birləşmiş qalmalıdır ki, istənilən iki nöqtə arasında neftin nəqli mümkün olsun.
Hər bir boru kəmərini təmir üçün sistemdən çıxarmaq üçün tələb olunan xərc məlumdur. Mühəndislərə kömək edin və büdcə məhdudiyyətini nəzərə alaraq şəbəkəni tam birləşmiş vəziyyətdə saxlayaraq texniki xidmətə götürmək mümkün olan maksimum sayda boru kəmərini müəyyən edin.
Birinci sətirdə — düyünlərin sayı, — boru kəmərlərinin sayı və mövcud texniki xidmət büdcəsi verilir (2 \le n \le 50000, 1 \le m \le 10^5, 0 \le s \le 10^{18}).
Növbəti sətirdə hər bir boru kəməri üçün onun birləşdirdiyi iki düyünün nömrələri və texniki xidmət üçün tələb olunan xərc verilir (xərc 10^9-u aşmır).
Neft hər bir boru kəməri üzrə hər iki istiqamətdə daşına bilər və hər bir düyün cütü arasında ən çox bir boru kəməri mövcuddur.
Birinci sətirdə mühəndislərin texniki xidmətə çıxara biləcəyi maksimum boru kəməri sayını çap edin. İkinci sətirdə isə bu boru kəmərlərinin nömrələrini (girişdəki sıralama ilə, -dən başlayaraq) çap edin.
Nümunə 1