C. Нийтийн дайчилгаа

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

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

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

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

Берландын вант улс бол хоорондоо $n - 1$ төмөр замаар холбогдсон $n$ хотуудын бүрдэл юм. Зам бүр ялгаатай яг хоёр хотыг хооронд нь холбодог. Хот бүрийн хувьд уг хотоос нийслэлрүү галт тэргээр явах зам бий.

$i$-р хотод $i$ дугаартай цэргийн хэлтэс байх ба хэлтэс бүр $a_{i}$ тоогоор тодорхойлогдоно. Энэ нь давуу байдлыг илтгэх ба бага тоо нь уг хэлтсийн их давуу байдлыг илтгэнэ. Бүх $a_{i}$ утгууд ялгаатай.

Нэг өдөр Берландын хаан Агуу Берл нийтийн дайчилгаа зарласан ба үүний тулд хэлтэс бүр нийслэлд ирэх ёстой. Өдөр бүр нийслэлээс бусад бүх хотоос галт тэрэг явдаг. Мөн өдөрт яг $n - 1$ галт тэрэг явна. Галт тэрэг бүр нийслэлрүү явах ба хөдөлгөөнөө дараагийн өдөр эсрэг талын эцсийн цэгт дуусгана. Галт тэрэг нэг явалтандаа тээвэрлэж чадах хэлтсүүдийн хамгийн их тоогоор илэрхийлэгдэх тодорхой $c_{j}$ багтаамжтай. Галт тэрэг бүр нийслэлрүү явах зайг багасгах чиглэлд явна. Мөн галт тэрэг бүр нийслэлрүү явахдаа нэг хотоос хөрш хотруу чиглэсэн төмөр замыг нэг л удаа туулна.

Хотод байгаа хэлтсүүдийн дундаас хамгийн эхэнд хамгийн бага $a_{i}$ тоотой нь галт тэргэнд эхэлж сууна, тэгээд дараагийн бага тоотой нь гээд галт тэрэг дүүрэх эсвэл бүх хэлтэс сууж дуусах хүртэл үргэлжилнэ. Мөн хэлтэс хотод хэдэн өдрийн турш үлдэх боломжтой.

Галт тэрэгний нэг хотоос өөр нэг хотод очих үйл явц яг $1$ өдөр үргэлжилнэ. Бүх хэлтсүүд яг зэрэг хөдөлж эхлэх ба нийслэлд ирнэ, өөр хаашаа ч явахгүй. Хэлтэс бүр энэ аялал хэр их хугацаа авахаас үл хамааран өөрийн хотоос нийслэл хүртэл энгийн замын дагуу явна.

Таны зорилго бол хэлтэс бүрийн хувьд Берландын нийслэлд хэдэн өдрийн дотор ирэхийг олох юм.

Оролт

Эхний мөрөнд нэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 5000$) байх ба Берландын хотуудын тоо юм. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$, байх ба энд $a_{i}$ нь $i$-р хотод байрласан хэлтсийн давуу эрх байна. Бүх $a_{1}, a_{2}, ..., a_{n}$ тоонууд ялгаатай ($1 ≤ a_{i} ≤ 10^{9}$). Дараагийн $n - 1$ мөрөнд төмөр замуудын тодорхойлолт байна. Тодорхойлолт бүр гурван бүхэл тоон утга $v_{j}, u_{j}, c_{j}$-с бүрдэх ба энд $v_{j}$, $u_{j}$ нь $i$-р замаар холбогдсон хотуудын дугаар байх ба $c_{j}$ нь уг зам дээрх галт тэргийн хамгийн их багтаамж байна ($1 ≤ v_{j}, u_{j} ≤ n, v_{j} ≠ u_{j}$, $1 ≤ c_{j} ≤ n$).

Гаралт

$t_{1}, t_{2}, ..., t_{n}$ дарааллыг хэвлэх ба энд $t_{i}$ нь $i$-р хотын хэлтэс нийслэл хотод ирэхэд шаардлагатай өдрийн тоо юм. Тоонуудыг зайгаар тусгаарла.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4
40 10 30 20
1 2 1
2 3 1
4 2 1
Гаралт
0 1 3 2 
Оролт
5
5 4 3 2 1
1 2 1
2 3 1
2 4 1
4 5 1
Гаралт
0 1 4 2 3 
Сэтгэгдлүүдийг ачааллаж байна...