Masala #0422

Azimjon yashab turgan qishloqga elektir tok o’tkazilmagan shu sabab bu qishloqqa elektir toki o’tkazilish rejalashtirildi. Hozirda faqatgina Azimjonning uyigagina tok yetib keldi. Bu qishloqda jami \(N\) ta uy mavjud bo’lib(uylar 1 dan \(N\) gacha raqamlangan) va Azimjon yashaydigan uy raqami 1 ga teng. Endi bu qishloqning mahallakomi kerakli tashkilotga murojat qildi har bir xonadonga elektir tokini Azimjon yashaydigan uydan kabel tortish kerak ekenligini va tortiladigan kabel uzunligi minimal bo’lish kerak ekenligini aytdi chunki mahallakom imkon qadar kam harajat qilishni istaydi. Tashkilot xodimlari kelib bu qishloqni yaxshilab o’rganib chiqdi ya’ni \(u_i\) uydan \(v_i\) uylarga kabel tortish mumkun ekanligini va ular o’rtasidagi masofalarni qog’ozga yozib chiqdi. Kabelning metiri \(X\) so’m tursa, tashkilot xodimlari yozib olgan ma’lumotlariga asosan barcha uylarga kabel tortish uchun mahallakom qancha mablag’ sarflashini aniqlang.

Misol: 3 ta uy uchun chizma tasvirlangan. 1-chizmada barcha bog’lanishlar va ular o’rtasidagi masofa tasvirlangan. 2-chizmada barcha uylarga elektir toki yetib borgandan so’ng holati tasvirlangan bu yerda qizil chiziqlar kabel hisoblanadi.

Kirish fayilining birinchi satirida uchta son \(N, K, X (2 \le N, K, X \le 5*10^6)\) mos ravishda xonadonlar soni, ikki xonadonni bog’lanishlar soni va bir metir kabel narxi. Kiyingi \(K\) ta satirda uchtadan son \(u,v,w(1 \le u,v,w \le N)\) bular \(u\)-raqamli uydan \(v\)-raqamli uyga kabel tortish mumkunligi yoki teskarisi va bu ikki uy o’rtasidagi masofa \(w\) ga teng.

Chiqish fayilida mahallakom eng kamida qancha harajat qilishi kerak ekanligini chop eting.