Laiko ribojimas: 3s

Atminties ribojimas: 256MB

Duomenų failas: valymas.in

Rezultatų failas: valymas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Sniego valymas

Atrodo, orai šįkart ignoruoja Užgavėnes ir pavasarį – Bitiškyje ir vėl prisnigo! Kadangi oficialiai žiema jau baigėsi, dauguma sniego valytojų atostogauja. Bet ryte žmonės turės vykti į darbą, taigi nors ir teliko viena darbinga valymo mašina, privalu švariai nuvalyti visas gatves...

Bitiškyje yra N sankryžų sujungtų N-1 gatve. Tarp kiekvienos sankryžų poros egzistuoja vienintelis kelias, bei kiekvienos gatvės ilgis lygus 1 km. Gatvės gali būti padengtos skirtingu sniego sluoksniu ir todėl norint nuvalyti kai kurias gatves pro jas gali tekti pravažiuoti keletą kartų.

Žinoma, sniego valytojas nori šį varginantį darbą įveikti kuo greičiau. Kokį mažiausią atstumą jam reikės nukeliauti, kad nuvalytų visą sniegą? Darbą jis gali pradėti ir baigti bet kurioje sankryžoje.

Pradiniai duomenys

Pirmoje eilutėje – skaičius N (2\\leqN\\leq5\\cdot10^5). Tolesnėse N-1 eilučių yra po tris sveikuosius skaičius A_i, B_i ir S_i, aprašančius gatves (1\\leqA_i,B_i\\leqN; A_i\\neqB_i; 1\\leqS_i\\leq10^5). i-oji gatvė jungia sankryžas, kurių numeriai yra A_i ir B_i, o norint nuvalyti visą sniegą šia gatve reikia pravažiuoti S_i kartų.

Rezultatai

Išveskite vieną skaičių – mažiausią atstumą kilometrais, kurį turi nukeliauti valytojas viso sniego nuvalymui.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
6
1 4 1
4 2 1
5 3 1
6 5 1
4 6 2
 
8