Masala B

Robolandiya mamlakatida \(N\) ta shahar mavjud. Shaharlar orasida \(N-1\) ta ikki yo‘nalishli yo‘l qurilgan. Bu yo‘llar shunday ulangan-ki, har qanday shahardan boshqasiga bevosita yoki bir nechta shaharlar orqali borish mumkin (ya’ni, graf daraxt shaklida).

Har bir yo‘l ikki shaharning orasini bog‘laydi va uning ustida \(W_{i}\) soni yozilgan. Qo‘shni shaharlar deb, orasida bevosita yo‘l mavjud bo‘lgan shaharlar juftligiga aytamiz. Agar kimdir bir shahardan uning qo‘shnisiga o‘tmoqchi bo‘lsa, uning pasport kuchi kamida shu yo‘l qiymatiga (\(W_{i}\)) teng bo‘lishi kerak. Kuch qiymati \(w\) bo‘lgan pasport aynan \(w\) tangaga tushadi.

Shunday qilib, ikki shahar \(a\) va \(b\) orasida sayohat qilish uchun pasport kuchi marshrutdagi eng katta \(W_{i}\) qiymatiga teng bo‘lishi kifoya. Ya’ni, siz tanlagan yo‘ldagi yo‘llar orasidagi maksimal qiymatni qoplash zarur.

Sizning vazifangiz: barcha juftliklar uchun \((1 \le i < j \le N)\) sayohat qilish uchun zarur bo‘lgan minimal pasport narxini hisoblang va ularning yig‘indisini toping.

Birinchi qatorda bitta butun son \(N\) (\(1 \le N \le 2 \times 10^{5}\)) — shaharlar soni.
Keyingi \(N-1\) qatorda uchta butun son \(a, b, W\) (\(1 \le W \le 10^{6}\)) beriladi — bu \(a\) va \(b\) shaharlari orasida qiymati \(W\) bo‘lgan yo‘l mavjudligini bildiradi.

Bitta butun son chiqaring — barcha \(\frac{N(N-1)}{2}\) juftlik uchun minimal pasport narxlari yig‘indisi.