Simon Hörümçək
Mosquito problemi çərçivəsində, həşəratların çoxalma qabiliyyətlərinin nə qədər yüksək olduğunu müşahidə etdiniz. Xoşbəxtlikdən, insanlar üçün həşəratların populyasiyasını azaltmağa kömək edən təbii düşmənlər də mövcuddur. Hörümçəklər, ən yaxşı məlum olan həşərat yırtıcıları arasında yer alır, buna görə də onları bu problem dəstinə daxil etməyimiz təəccüblü deyil.
Simon Hörümçək bu yay çoxlu həşərat yedi və kökəldi. Torunun iplikləri tezliklə onu daşımaq üçün çox nazik olacaq və buna görə də onları möhkəmləndirməlidir. Kök hörümçəklər də tənbəl olduğundan, Simon mümkün qədər az material istifadə etmək istəyir — bilirsiniz ki, hörümçəklər tor qurmaq üçün materialı özləri istehsal etməlidirlər. Nəhayət, o, yalnız bəzi iplikləri möhkəmləndirməyə qərar verdi, lakin vacibdir ki, torunun hər bir düyünü möhkəmləndirilmiş bağlantılar vasitəsilə əlçatan olsun.
Əlavə olaraq, Simon boş vaxtını möhkəmləndirilmiş bağlantılardan birində keçirməyi planlaşdırır və bu bir bağlantının uzun olmasını istəyir. Buna görə də, bütün möhkəmləndirilmiş bağlantıların ümumi uzunluğunu hesablayarkən, ən uzun möhkəmləndirilmiş bağlantının uzunluğu çıxılacaq əvəzinə əlavə ediləcək. Simon'a bu şərtlər altında mümkün olan ən az ümumi uzunluğa malik bağlantıların hansının möhkəmləndirilməli olduğunu qərar verməyə kömək edin.
Giriş verilənləri
Giriş bir neçə torun təsvirlərindən ibarətdir. Hər bir təsvirin ilk sətiri torun düyünlərinin sayı N (2 ≤ N ≤ 2000) və düyün cütləri arasındakı bağlantıların sayı M (0 ≤ M ≤ 1000000) olan iki rəqəmi ehtiva edir. Sonrakı M sətirin hər biri bir bağlantını təsvir edir. Hər bir bağlantının təsviri üç müsbət tam ədəd u_i, v_i, i ehtiva edir, burada u_i və v_i (1 ≤ u_i, v_{i }≤ N və u_i ≠ v_i) bağlantı ilə birləşdirilən iki düyündür və i onun uzunluğudur (1 ≤ i ≤ 100000).
Çıxış verilənləri
Hər bir tor üçün, verilmiş bütün şərtlər altında möhkəmləndirilmiş bağlantıların mümkün olan ən az ümumi uzunluğunu bir sətirdə çap edin. Unutmayın ki, ümumi uzunluq bütün möhkəmləndirilmiş bağlantıların uzunluqlarının cəmi minus ən uzun möhkəmləndirilmiş bağlantının uzunluğunun ikiqatıdır.
Əgər hər bir düyündən digər hər bir düyünə bağlantılar ardıcıllığı vasitəsilə çatmaq mümkün deyilsə, onda xərci əvəzinə "disconnected" çap edin.