E. Агуа Шаасс

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Агуа Шаасс бол бол Драхт эзэнт гүрний шинэ хаан юм. Эзэнт гүрэн нь $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 стриймийг ашиглана уу.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
3
1 2 2
1 3 4
Гаралт
12
Оролт
6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
Гаралт
29
Оролт
6
1 3 1
2 3 1
3 4 100
4 5 2
4 6 1
Гаралт
825
Сэтгэгдлүүдийг ачааллаж байна...