C. Зохион байгуулах асуултууд

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

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

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

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

Улс хоорондоо төмөр замын сүлжээгээр холбогдсон $n$ ширхэг хотоос бүрдсэн. Улсын тээвэрлэлтийн сүлжээ ихэд өндөр хөгжсөн бөгөөд сүлжээ нь хамгийн цөөн тооны буюу $(n - 1)$ ширхэг замаас бүтсэн (өөрөөр хэлвэл, замуудын зураг нь мод хэлбэртэй). $i$ дэхь зам нь $a_{i}$ ба $b_{i}$ хотуудыг $l_{i}$ километр замаар хооронд холбодог.

Тээвэрлэлтийн сүлжээг ГТЗ (Гайхалтай Төмөр Зам) гэх улсын тээвэрлэлтийн компани хариуцан ажилладаг. Үнийн тогтолцоог энгийн байлгах үүднээс галт тэрэгний үнийг ганцхан удаа төлдөг болгожээ. $t$ километр зам явахын тулд та бөрл төлөх ёстой. Та урт аялалыг олон жижиг хэсэгт хуваан тус тусд нь төлж болохгүй (онцгой төмөр замын цагдаа (ТЗЦ) нь хууль зөрчигдөхгүй байхыг хянадаг).

Нэгэн маш том програм хангамжын компани програмчлалын тэмцээн зохиохоор шийджээ. Интернетээр хэд хэдэн үе шатууд явуулсаны дараа эцсийн шатны оролцогчдын нэрсийг зохион байгуулах комисст хүлээлгэн өгч хаана эцсийн шатыг явуулахыг шийдүүлэхээр болжээ. Энэхүү компани нь тухайн улсын $n$ ширхэг хотын аль ч хотод амархан эцсийн шатыг зохион байгуулж чадна. Харин зөв хотыг сонгох гол шалтгаан нь эцсийн шатанд үлдсэн оролцогчдийн нийт галт тэрэгний тасалбарын төлбөр юм. Бид $i$ дэхь хотод $w_{i}$ ширхэг эцсийн шатны оролцогч амьдардагыг мэднэ.

Компаны ажилчдад хамгийн бага аялалын зардалтай байхаар эцсийн шатыг аль хотод явуулахыг олж өгч тусална уу.

Оролт

Эхний мөрөнд улсын нийт хотын тоо болох бүхэл тоо $n$ ($1 ≤ n ≤ 200 000$) өгөгдөнө.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоонууд $w_{1}, w_{2}, ..., w_{n}$ ($0 ≤ w_{i} ≤ 10^{8}$) өгөгдөнө. Эдгээр нь хот болгонд байгаа эцсийн шатны оролцогчдын тоо.

Дараагийн $(n - 1)$ ширхэг мөрөнд төмөр замын тайлбарууд өгөгдөнө. Энд $i$ дэхь мөрөнд $i$ дэхь замын тайлбар буюу 3-н бүхэл тоонууд $a_{i}$, $b_{i}$, $l_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$, $1 ≤ l_{i} ≤ 1000$) өгөгдөнө.

Гаралт

2 бүхэл тоо хэвлэнэ үү. Энд эхний тоо нь бүхэл тоо байх бөгөөд эцсийн шатыг явуулж болох хамгийн тохиромжтой хотын дугаар $f$-г хэвлэнэ үү. Дараагийн тоо нь бүх оролцогчдыг тохиромжтой хотод ирэх зардал буюу нэг жинхэнэ тоо $c$-г хэвлэнэ үү. Таны хариултыг дараах 2 шалгуурыг нэгэн зэрэг хангасан тохиолдолд зөвөөр тооцно:

  1. Хэвлэсэн $c$ тооны харьцангуй болон үнэмлэхүй алдаа нь $f$ хотод эцсийн шатыг зохион байгуулах зардалтай харьцуулан $10^{ - 6}$-г хэтрэхгүй байвал;
  2. Хэвлэсэн $c$ тооны харьцангуй болон үнэмлэхүй алдаа нь шүүгчийн хариутай харьцуулан $10^{ - 6}$-г хэтрэхгүй байвал.

Хэрвээ олон хариулт байвал дурын нэгийг хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
5
3 1 2 6 5
1 2 3
2 3 1
4 3 9
5 3 1
Гаралт
3 192.0
Оролт
2
5 5
1 2 2
Гаралт
1 14.142135623730951000

Тэмдэглэл

Эхний жишээнд хамгийн тохиромжтой хот нь $3$ бөгөөд үүний зардал нь бөрл болно.

2 дахь жишээнд аль ч хотыг сонгосон, та 5-н оролцогчид зардлын мөнгө өгнө. Тиймээс та оролцогч болгоны зардалд бөрл өгөх шаардлагатай.

Сэтгэгдлүүдийг ачааллаж байна...