Qar problem deyil

YETI Mühəndislik-Texnologiya İnstitutunun (YETI), Şnoubloyanın şimalında yerləşən, iki problemi var: qar və pul. Xüsusilə, qar çox, pul isə azdır. Hər qış (həmçinin payız və yazda da) kampus qarla örtülür və kampusun binalarını birləşdirən səkilər keçilməz olur. İşini davam etdirmək üçün YETI kampusun binalarını birləşdirən səkiləri qardan təmizləməlidir. Büdcə problem olduğuna görə, bu səkilər hər hansı iki bina arasında yol yaratmağa imkan verən minimal dəstdir.

Yeni səkilərin tikintisindən imtina etməklə qənaət edilən pulla YETI iki qar təmizləyici maşın alıb. Onların köməyi ilə qar təmizləmək üçün iki işçi qar təmizləyiciləri saxlanıldığı binadan (və ya binalardan) çıxarır və səkilərlə itələyərək qarı təmizləyir. Hər səki ən azı bir dəfə keçilməlidir. Hər qar təmizləyici işini bitirdikdən sonra o anda yaxın olduğu binada saxlanılır (və növbəti qar yağışında qar təmizləyicilər əks istiqamətdə hərəkət edəcək — və beləliklə, on bir aylıq qar mövsümü boyunca).

YETI-nin texniki heyəti qar təmizləyicilərin saxlanılması üçün binaları seçmək və onların hərəkət edəcəyi marşrutları layihələndirmək istəyir ki, iki maşının soyuqda keçəcəyi ümumi məsafəni minimuma endirsinlər (həm qiymətli avadanlığı, həm də işçiləri donmadan qorumaq üçün). Qeyd edək ki, marşrutlar artıq təmizlənmiş səkilərdən keçməyi də əhatə edə bilər, J.1 şəkilində göstərildiyi kimi, burada giriş nümunəsi 1 üçün səki sxeminin optimal həlli göstərilib.

YETI bu məsələni həll etmək üçün kompüter elmləri şöbəsinə müraciət etdi, lakin o, 2006-cı ilin Böyük qar fırtınası zamanı məhv oldu, buna görə də sizdən kömək istəyirlər.

Giriş verilənləri

Birinci sətirdə YETI kampusunda binaların sayı olan $n(4\le n\le 10^5)$ tam ədədi verilib. Binalar $1$-dən $n$-ə qədər nömrələnib. Qalan $n-1$ sətirdə isə üç tam ədəd $a$, $b$ və $d$ verilib, bu da $a$ və $b(1\le a,b\le n,a\ne b)$ binaları arasında uzunluğu $d(1\le d\le 500)$ olan səkinin mövcudluğunu göstərir.

Çıxış verilənləri

Qar təmizləyicilərin bütün səkiləri təmizləməsi üçün keçməli olduğu minimal ümumi məsafəni çıxarın.

Nümunələr