A. Тойрон зам

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

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

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

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

Өнөө үед замын хөдөлгөөний аюулгүй байдлыг хангах, түгжрэл бууруулах зорилгоор нэг урсгалтай замыг дэлхий даяар нэвтрүүлсэн байна. Берландын засгийн газар ч энэ шинэ хандлагыг нэвтрүүлэхээр шийдэв. Ер нь Берландын $n$ тооны бүх хотууд $n$ тооны хоёр урсгалтай замаар шууд холбогдсон. Өөрөөр хэлбэл хот тус бүр өөр хоёр хоттой шууд холбогдсон байх ба хот тус бүрээс бусад аль ч хот руу хүрэх боломжтой байв.

Берландын засгийн газар $n$ замууд дээр нэг урсгал нэмсэн боловч удалгүй зарим хотоос өөр бусад хотууд руу хүрэх боломжгүй болсон нь тодорхой болов. Зам тус бүр яг хаашаа хүрэх, дахин чиглүүлэх зардал нь байгаа нь мэдэгдэх байна.

Бүх хотоос дурын нэг хот руу хүрэх боломжтой болгох үүднээс замыг дахин чиглүүлэхэд засгийн газар хамгийн багадаа хичнээн хэмжээний мөнгө зарцуулах вэ?

Оролт

Эхний мөр нь $n$ ($3 ≤ n ≤ 100$) гэсэн бүхэл тоо агуулах ба энэ нь Берланд дахь нийт хот болон замуудын тоог харуулна. Зам тус бүр $a_{i}$, $b_{i}$, $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, 1 ≤ c_{i} ≤ 100$) гэсэн гурван бүхэл тоогоор тодорхойлогдох ба энэ нь $a_{i}$ хотоос $b_{i}$ хот руу хүрэх $c_{i}$ замыг дахин чиглүүлэх зардлыг илэрхийлнэ.

Гаралт

Бүх хотоос дурын нэг хот руу хүрэх боломжтой болгох үүднээс замыг дахин чиглүүлэхэд засгийн газар хамгийн багадаа зарцуулагдах ёстой мөнгөн дүнг бүхэл тоогоор гарга.

Орчуулсан: Энхгэрэл

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

Оролт
3
1 3 1
1 2 1
3 2 1
Гаралт
1
Оролт
3
1 3 1
1 2 5
3 2 1
Гаралт
2
Оролт
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
Гаралт
39
Оролт
4
1 2 9
2 3 8
3 4 7
4 1 5
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...