Мистер В#10503
Dostlar Mister V-yə ədəd muncuq hədiyyə etdilər, bunlar -dən -ə qədər tam ədədlərlə nömrələnmişdir. Mister V bu muncuqları (n-1) ədəd sapla birləşdirərək bir boyunbağı yaratdı. Proqramçı olan Mister V, boyunbağını ağacvari bir quruluşda hazırladı.
Mister V boyunbağını belə qurdu: əvvəlcə bir başlanğıc muncuq seçdi, sonra (n-1) dəfə boyunbağına bir muncuq əlavə etdi. Muncuqları əlavə etmək üçün iki üsuldan birini seçə bilərdi: ya boyunbağıya aid olan bir muncuq seçib onu boyunbağıya aid olmayan bir muncuqla qırmızı sapla birləşdirirdi, ya da boyunbağında qırmızı sapla birləşdirilmiş bir muncuq cütünü seçib onları ayırır və hər birini yeni əlavə etdiyi muncuqla mavi sapla birləşdirirdi.
Boyunbağının muncuqlarını birləşdirən sapların uzunluqları müxtəlif ola bilər.
Mister V boyunbağının strukturunu yazdı və onu Missis V-yə hədiyyə etdi. Lakin, sapların rənglərini unutdu. Ona boyunbağının mavi saplarının uzunluqlarının mümkün olan maksimum cəmini tapmağa kömək edin, çünki bu dəyər onun üçün çox maraqlıdır.
Birinci sətir bir tam ədəd (1\le n\le 2\cdot 10^5) — boyunbağının muncuqlarının sayını ehtiva edir.
Sonrakı n-1 sətirin hər biri üç tam ədəd , və (1\le u<v\le n, 1\le l\le 10\,000) ehtiva edir — müvafiq sapın birləşdirdiyi muncuqların nömrələri və onun uzunluğu.
Bir tam ədəd çıxarın — boyunbağının mavi saplarının uzunluqlarının mümkün olan maksimum cəmi.
Nümunə 1
Nümunə 2
Birinci nümunədə Mister V boyunbağını nömrəli muncuqdan başlaya bilərdi, sonra nömrəli muncuğu nömrəli muncuqla qırmızı sapla birləşdirə bilərdi, sonra və nömrəli muncuqları ayırıb və , həmçinin və nömrəli muncuqları mavi saplarla birləşdirə bilərdi, sonra və nömrəli muncuqları qırmızı sapla birləşdirə bilərdi və son addımda və nömrəli muncuqları qırmızı sapla birləşdirə bilərdi. Beləliklə, mavi sapların uzunluqlarının cəmi olacaq.
( bal): 1\le n\le 10;
( bal): 1\le n\le 200;
( bal): 1\le n\le 10000;
( bal): əlavə məhdudiyyətlər olmadan.