Агуа Шаасс бол бол Драхт эзэнт гүрний шинэ хаан юм. Эзэнт гүрэн нь $n$ хоттой ба хотууд $n-1$ хоёр чиглэлт замаар холбогдсон. Бүх замууд тодорхой урттай ба хос хотыг холбодог.

Сүр хүчит агуа Шаасс нэг замыг нурааж яг тийм урттай замыг өөр хотуудын дунд барихаар шийджээ. Тэрээр дурын $2$ хотын хооронд зорчиж болохоор барих ёстой. Тэрээр өмнөх замаа дахин тавьсан ч болно.

Та түүний зөвлөгч бөгөөд бүх хот хоорондын замын нийлбэр нь хамгийн бага байхаар замыг тавина уу. Мөн уг нийлбэрийг олно уу.

Оролт

Эхний мөрөнд эзэнт гүрэнд байх хотын тоо $n$ ($2 ≤ n ≤ 5000$) байна. Дараагийн $n-1$ мөрөнд $a_i$, $b_i$, $w_i$ тоонууд байх ба $a_i$, $b_i$ хотын хооронд $w_i$ урттай зам байгааг илтгэнэ ($1 ≤a_i, b_i ≤ n$, $a_i ≠ b_i$, $1 ≤ w_i ≤ 10^6$).

Гаралт

Бүх хотын хоорондох зай нь хамгийн бага байх нийлбэрийг ол.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.