Neft müqaviləsi

"'markdown Neft strateji baxımdan çox mühüm bir resursdur. Son zamanlar Antarktika Birləşmiş Ştatları neftlə zəngin Kari ölkəsinə hücum edərək onun neft nəqliyyat sisteminə nəzarət etməyə çalışır. Bu sistem, neft mənbələri ilə ölkənin əsas şəhər və limanlarını birləşdirən boru kəmərlərindən ibarətdir. Sistem elə qurulub ki, hər hansı bir qovşaqdan digərinə neft daşımaq mümkündür.

Lakin, Kari milli qüvvələri bu vəziyyətdən narazıdır. Onlar mütəmadi olaraq terror aktları törədərək bəzi neft kəmərlərini partladırlar. Son zamanlar terroristlər bir sıra partlayışlar həyata keçirmək qərarına gəliblər və neft kəməri sisteminə mümkün qədər çox zərər vurmaq istəyirlər.

Hər bir boru kəməri üçün terroristlər onu partlatmağın dəyərini bilirlər. Onların sabit miqdarda pulu var və bu məbləğə mümkün qədər çox boru partlatmaq istəyirlər. Lakin, ölkənin müxtəlif bölgələrində özləri üçün hələ də neftə ehtiyacları olduğundan, sistemin hələ də hər hansı bir qovşaqdan digərinə neft daşımaq imkanında olmasını istəyirlər. Onlara hansı boruları partlatmaq lazım olduğunu müəyyən etməyə kömək edin.

Giriş verilənləri

Birinci sətir terroristlərin sahib olduğu qovşaqların sayı $n$, boru kəmərlərinin sayı $m$ və pul miqdarı $s(2\le n\le 50000,1\le m\le 10^5,0\le s\le 10^{18})$ göstərir. Növbəti $m$ sətir boru kəmərləri haqqında məlumatı — boru kəməri ilə birləşdirilən qovşaqların nömrələri və onun partlatma dəyərini (bu $10^9$-dan çox deyil) ehtiva edir.

Neft hər bir boru kəməri boyunca hər iki istiqamətdə ötürülə bilər, hər iki qovşaq bir boru kəmərindən çoxu ilə birləşdirilməyib.

Çıxış verilənləri

Birinci sətirdə terroristlərin partlada biləcəyi maksimum boru kəmərlərinin sayını göstərin. İkinci sətirdə bu boru kəmərlərinin nömrələrini göstərin (onlar giriş məlumatlarında göründükləri ardıcıllıqla $1$-dən başlayaraq nömrələnir). "'

Nümunələr