Muallif: __thecrash__
F. Chumolilar uyasi
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Yer ostida katta chumolilar uyasi bor. Uya \(n\) ta xonadan iborat, xonalar \(1\) dan \(n\) gacha raqamlangan. Ular \(n - 1\) ta tunnel bilan ulangan, \(i\)-tunnel \(u_i\) va \(v_i\) xonalarni bog'laydi va uning uzunligi \(w_i\) millimetr. Chumolilar tunnellar bo'ylab ikki tomonga ham yura oladi. Istalgan xonadan istalgan boshqa xonaga tunnellar orqali borish mumkin, buning yo'li esa yagona.
Chumolilar malikasi yosh ishchi chumolilar uchun yugurish musobaqasi o'tkazmoqchi. Buning uchun u uyadagi bir-biridan eng uzoqda joylashgan ikki xonani start va marra qilib tanlamoqchi. Ikki xona orasidagi masofa ularni bog'lovchi yo'ldagi tunnellar uzunliklari yig'indisiga teng.
Malikaga yordam bering, uyadagi ikki xona orasidagi eng katta masofani toping.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 2 \cdot 10^5\)) xonalar soni.
Keyingi \(n - 1\) ta qatorning har birida uchta butun son \(u_i\), \(v_i\) va \(w_i\) (\(1 \le u_i, v_i \le n\), \(u_i \ne v_i\), \(1 \le w_i \le 10^9\)) tunnel bog'laydigan xonalar va tunnel uzunligi.
Chiquvchi ma'lumotlar
Ikki xona orasidagi eng katta masofani chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
5 1 2 3 2 3 4 2 4 2 4 5 6 |
12 |
| 2 |
4 1 2 5 1 3 5 1 4 1 |
10 |
Izoh
Birinchi misolda eng uzoq xonalar \(3\) va \(5\). Ular orasidagi yo'l \(3 \to 2 \to 4 \to 5\), uzunligi \(4 + 2 + 6 = 12\).
Ikkinchi misolda eng uzoq yo'l \(2 \to 1 \to 3\), uzunligi \(5 + 5 = 10\).