D. Мөнхийн ялалт

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

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

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

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

Валэрианчууд Шапурт эзлэгдэв. Энэ нь үнэхээр агуу ялалтын нэг байсан тул Шапур, уулан дээр Валэрианчуудын ялагдсан үйл явдлыг сийлэхээр шийдэв. Тиймээс түүний ялалтыг мөнхлөх хамгийн сайн газрыг олох ёстой болов.

Тэрээр хамгийн сайн тохирох уулыг олохоор Персийн бүх $n$ хотуудад зочлохоор шийдсэн боловч саяын дайны дараа тэр их ядарсан байсан тул их зам туулахыг хүссэнгүй. Тиймээс тэр $n$ хот бүрт ядаж нэг удаа очих боломжит хамгийн бага замыг туулахыг хүсэв. Персийн хотууд хоёр урсгалтай замуудаар холбогддог. Аль ч хотоос өөр аль ч хот руу эдгээр замуудаар дамжин очиж болох зам цор ганц байдаг.

Бүх хотууд $1$-ээс $n$ тоогоор дугаарлагдсан. Шапур яг одоо $1$ хотод байгаа бөгөөд боломжит хамгийн богино аяллаар бүх хотоор дайрахыг хүсч байна. Тэр аяллаа аль ч хотод дуусгаж болно.

Түүнийг хэр их аялах хэрэгтэйг нь олоход Шапурт тусална уу.

Оролт

Эхний мөр нийт хотын тоо болох $n$ ($1 ≤ n ≤ 10^5$) бүхэл тоог агуулна.

Дараагийн $n - 1$ мөр бүр $x_i$, $y_i$, $w_i$ ($1 ≤ x_i, y_i ≤ n$, $0 ≤ w_i ≤ 2 × 10^4$) гурван бүхэл тоог агуулна. Энд $x_i$, $y_i$ нь замын хоёр төгсгөл бөгөөд $w_i$ нь уг замын урт.

Гаралт

Шапурын аяллын хамгийн богино аяллын урт болох ганц бүхэл тоо.

Орчуулсан: Sugardorj

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

Оролт
3
1 2 3
2 3 4
Гаралт
7
Оролт
3
1 2 3
1 3 3
Гаралт
9
Сэтгэгдлүүдийг ачааллаж байна...