E. Шахуургын станцууд

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

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

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

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

Галзуу эрдэмтэн Майк ажилд томилогдсон. Түүний ажил бол ус шахуургын станцуудын системийг удирдах юм.

Системд $n$ ширхэг шахуургын станц байгаа ба 1-c $n$ хүртэл дугаарлагдсан. Зарим хос станцууд хоорондоо хос чиглэлтэй (аль ч чиглэлд ус урсах боломжтой гэхдээ тухайн агшинд нэг чиглэлд л урсана) хоолойгоор холбогдсон. Хоолой бүрийн хувьд та тухайн хоолойгоор нэг цагийн хугацаанд урсах боломжтой усны хамгийн их хэмжээг илэрхийлсэн багтаамжийг мэдэж байгаа. Шахуургын станц бүр зарим станцаас ирж буй усыг бусад станцруу хоолойгоор шахаж чадна. Нэг цагийн хугацаанд станцруу орж байгаа нийт усны хэмжээ станцаас гарч байгаа усны хэмжээтэй тэнцүү.

Станцууд хооронд ус шахах нь Майкийн хариуцах зүйл юм. Дээр тодорхойлсон дүрмүүдийн дагуу $a$ станцаас $b$ станцруу нэг цагийн хугацаанд тодорхой хэмжээний ус хоолойгоор дамжуулах боломжтой. Энэ хугацааны туршид бусад станцаас $a$ станцруу урсгал явах боломжгүй ба $b$ станцаас урсгал гарах боломжгүй. Хэдий $a$ станцаас дурын хэмжээний ус гарч $b$ станцад дурын хэмжээний ус орж болох боловч хэрвээ нэг цагийн хугацаанд $a$ станцаас нийт $x$ литр ус урсан гарсан бол Майк цалин дээрээ $x$ боллар нэмж авна.

Гэрээний дагуу Майк цалин авахын тулд $n - 1$ өдрийн турш ажиллах хэрэгтэй. Эхний өдөр Майк $v_{1}$ ба $v_{2}$ станцуудыг сонгох ба нэг цагийн хугацаанд $v_{1}$-с $v_{2}$-рүү тодорхой хэмжээний ус шахна. Дараа нь $i$-р өдөр Майк өмнө нь сонгоогүй $v_{i + 1}$ станцыг сонгох ба $v_{i}$ станцаас $v_{i + 1}$ станцруу нэг цагийн хугацаанд тодорхой хэмжээний ус шахна. Түүний $i$-р өдөрт шахсан усны хэмжээ нь $(i - 1)$-р өдөрт шахсан усны хэмжээнээс хамаарахгүй.

Майк өөрийн төслийнхөө хугацаанд цуглуулж чадах хамгийн их болларыг цуглуулах шаардлагатай. Майкд хамгийн их цалин авах боломж үүсгэх станцуудын дугаарыг агуулсан $v_{1}$, $v_{2}$, $...$, $v_{n}$ хэлбэртэй дараалал олоход нь туслана уу.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ба $m$ ($2 ≤ n ≤ 200$, $1 ≤ m ≤ 1000$) байх буюу харгалзан систем дахь станцуудын тоо болон хоолойнуудын тоо юм. Дараагийн $m$ мөрийн $i$-р мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоо $a_{i}$, $b_{i}$ ба $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$, $1 ≤ c_{i} ≤ 100$) байх буюу харгалзан $i$-р хоолойгоор холбогдсон станцуудын дугаар ба хоолойн багтаамж байна. Ямар ч хоёр станцын хооронд нэгээс олон хоолой байхгүй ба ямар ч хоёр станцын хооронд тэдгээрийг холбосон хоолойн зам байна.

Гаралт

Эхний мөрөнд Майкийн цуглуулж чадах хамгийн их цалинг илэрхийлэх нэг бүхэл тоог хэвлэ.

Хоёр дахь мөрөнд станцуудын дугаарыг илэрхийлсэн $v_{1}$, $v_{2}$, $...$, $v_{n}$ тоонуудын дараалал дахь 1-с $n$ хүртэлх $n$ тооны зайгаар тусгаарлагдсан дараалал байна. Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

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

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

Оролт
6 11
1 2 10
1 6 8
2 3 4
2 5 2
2 6 3
3 4 5
3 5 4
3 6 2
4 5 7
4 6 2
5 6 3
Гаралт
77
6 2 1 5 3 4 
Сэтгэгдлүүдийг ачааллаж байна...