Мистер В

Dostlar Mister V-yə $n$ ədəd muncuq hədiyyə etdilər, bunlar $1$-dən $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.

Giriş verilənləri

Birinci sətir bir tam ədəd $n$ ($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 $u$, $v$ və $l$ ($1\le u<v\le n$, $1\le l\le 10000$) ehtiva edir — müvafiq sapın birləşdirdiyi muncuqların nömrələri və onun uzunluğu.

Çıxış verilənləri

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ələr

Qeyd

Birinci nümunədə Mister V boyunbağını $3$ nömrəli muncuqdan başlaya bilərdi, sonra $3$ nömrəli muncuğu $5$ nömrəli muncuqla qırmızı sapla birləşdirə bilərdi, sonra $3$ və $5$ nömrəli muncuqları ayırıb $1$ və $3$, həmçinin $1$ və $5$ nömrəli muncuqları mavi saplarla birləşdirə bilərdi, sonra $1$ və $2$ nömrəli muncuqları qırmızı sapla birləşdirə bilərdi və son addımda $1$ və $4$ nömrəli muncuqları qırmızı sapla birləşdirə bilərdi. Beləliklə, mavi sapların uzunluqlarının cəmi $60$ olacaq.

Qiymətləndirmə

1. ($13$ bal): $1\le n\le 10$;

2. ($15$ bal): $1\le n\le 200$;

3. ($29$ bal): $1\le n\le 10000$;

4. ($43$ bal): əlavə məhdudiyyətlər olmadan.