Təlim
Мирко və Slavko Xorvatiyada keçiriləcək illik tandem velomarafonuna ciddi hazırlaşırlar. Onlar məşq üçün marşrut seçməlidirlər.
Ölkədə N şəhər və M yol var. Hər bir yol iki şəhəri birləşdirir və hər iki istiqamətdə hərəkət etmək mümkündür. Bu yollardan dəqiq N-1 daş döşənmişdir, qalan yollar isə döşənməmiş cığırdır. Xoşbəxtlikdən, yol şəbəkəsi elə qurulub ki, istənilən iki şəhəri yalnız daş döşənmiş yollardan ibarət bir yol birləşdirir. Başqa sözlə, N şəhər və N-1 daş döşənmiş yol ağac strukturunu təşkil edir.
Əlavə olaraq, hər bir şəhərdə ən çox 10 yol bitir.
Məşq marşrutu müəyyən bir şəhərdə başlayır, bəzi yollardan keçir və başladığı şəhərdə bitir. Mirko və Slavko yeni şəhərləri ziyarət etməyi sevirlər, buna görə də belə bir qayda qoyublar: heç vaxt eyni yerdən və eyni yoldan iki dəfə keçməmək. Məşq marşrutu istənilən şəhərdə başlaya bilər və bütün şəhərlərdən keçmək məcburiyyətində deyil.
Tandemdə arxa oturacaqda oturmaq daha asandır, çünki velosipedçi ön oturacaqda oturan tərəfdaş tərəfindən küləkdən qorunur. Buna görə də Mirko və Slavko hər şəhərdə yerlərini dəyişirlər. Məşq zamanı bərabər yük almaq üçün onlar cüt sayda yoldan ibarət marşrut seçməlidirlər.
Mirko və Slavkonun rəqibləri bəzi cığırları bloklamağa qərar veriblər ki, göstərilən tələblərə cavab verən məşq marşrutu qurmaq mümkün olmasın. Hər bir cığırın bloklanma qiyməti məlumdur (müsbət tam ədəd). Daş döşənmiş yolları bloklamaq mümkün deyil.
Şəhərlər və yolların təsviri əsasında göstərilən tələblərə cavab verən məşq marşrutunun mövcud olmaması üçün yolları bloklamaq üçün lazım olan ən az ümumi dəyəri tapan proqram yazın.
Giriş verilənləri
Giriş məlumatlarının ilk sətiri şəhərlərin və ümumi yolların sayını göstərən iki tam ədəd N və M ehtiva edir. (2 ≤ N ≤ 1000, N - 1 ≤ M ≤ 5000).
Növbəti M sətirdən hər biri bir yolu təsvir edən üç tam ədəd A, B və C (1 ≤ A, B ≤ N, 0 ≤ C ≤ 10000) ehtiva edir. A və B fərqlidir və birbaşa yol ilə birləşdirilən şəhərləri müəyyən edir. Əgər C = 0 - yol daş döşənmişdir; əks halda - bu bir cığırdır və C yolun bloklanma qiymətini göstərir.
Hər bir şəhərdə ən çox 10 yol bitir. İki şəhər birbaşa bir yoldan çox birləşdirilmir.
Çıxış verilənləri
Çıxış məlumatları yuxarıda təsvir edilən ən az ümumi dəyəri göstərən bir tam ədəd ehtiva etməlidir.