C. Берландын замын хөдөлгөөн

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

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

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

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

Берландын замын хөдөлгөөн нь бусад улсын замын хөдөлгөөнөөс маш их ялгаатай. Берландын нийслэл хот нь $n$ ширхэг замын уулзвар болон $m$ ширхэг замаас тогтдог. Зам болгон нь хос замын уулзварыг холбох ба ямар нэгэн хос замын уулзварын хооронд олон тооны зам байж болно. Зам болгоны хувьд бид үүний багтаамж болох $c_{i}$-г мэдэх юм. $c_{i}$-ын утга нь нэгж хугацаанд уг замын аль ч чиглэлд явж болох машинуудын хамгийн их тоог илэрхийлнэ. Зам болгоны хувьд машинууд нь 2 чиглэлийн аль нэгнийх нь дагуу явах юм. Өөрөөр хэлбэл машинууд нь нэгэн зэрэг 2 чиглэлд явж болохгүй гэсэн үг. Ямар нэгэн замын хөдөлгөөн гэдэг нь нэгж хугацаанд уг зам дагуу явж буй машинуудын тоог хэлнэ. ($a_{i}, b_{i}$) замын хувьд хэрэв замын хөдөлгөөн нь $b_{i}$-аас $a_{i}$ хүртэл явж байвал уг утга нь сөрөг байх юм. Мөн ямар нэгэн замын хөдөлгөөн нь бүхэл биш тоо байж болно.

Нийслэл хот нь 2 онцгой уулзвартай. Уулзвар 1 нь уг хот уруу нэвтрэх уулзвар ба уулзвар $n$ нь уг хотоос гарах уулзвар юм. Бүх уулзварын хувьд тухайн уулзвар дээрх замын хөдөлгөөн алдагдаагүй байх юм. Өөрөөр хэлбэл 1 болон $n$-р уулзвараас бусад бүх уулзварын хувьд ирж буй замын хөдөлгөөний нийлбэр нь гарж буй замын хөдөлгөөний нийлбэртэй тэнцүү байна.

Берландын нийслэлд замын хөдөлгөөн нь онцгой шинж чанартай байдаг. Дурын ($x, y$) хос замын уулзварын хувьд $x$-ээс $y$ хүртэлх ямар ч маршрут дагуух замын хөдөлгөөнүүдийн нийлбэр нь уг маршрутын сонголтоос хамааран өөрчлөгддөггүй. $x$-ээс $y$ хүртэлх маршрут дагуух замын хөдөлгөөнүүдийн нийлбэр гэдэг нь уг маршрутын бүх замууд дагуух замын хөдөлгөөнүүдийн нийлбэр байх юм. Хэрэв тухайн зам дагуух замын хөдөлгөөн нь $x$-ээс $y$ хүртэлх маршрут дээрх замуудын чиглэлээс эсрэг чиглэлд байвал уг замын хөдөлгөөн нь урдаа "хасах" тэмдэгтэй байна.

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

Оролт

Эхний мөрөнд уулзварын тоо болох эерэг бүхэл тоо $n$ өгөгдөнө ($2 ≤ n ≤ 100$). 2-дахь мөрөнд замуудын тоо болох бүхэл тоо $m$ ($1 ≤ m ≤ 5000$) өгөгдөнө. Дараагийн $m$ мөрөнд замуудын тайлбар өгөгдөнө. Зам болгон нь $a_{i}$, $b_{i}$, $c_{i}$ гэсэн 3-н тоо агуулах ба энд $a_{i}, b_{i}$ нь өгөгдсөн замаар холбогдох уулзваруудын дугаарыг илэрхийлэх бөгөөд $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$; $a_{i} ≠ b_{i}$; $0 ≤ c_{i} ≤ 10000$) нь уг зам дагуу явж болох хамгийн том замын хөдөлгөөнийг илэрхийлнэ.

Гаралт

Эхний мөрөнд нийслэл хотоор өнгөрөх хамгийн том замын хөдөлгөөнийг хэвлэнэ. Дараа нь $m$ мөрийн мөр болгонд харгалзах зам дагуу хөдлөх замын хөдөлгөөний хурдыг хэвлэнэ. Хэрэв тухайн чиглэл нь уулзваруудын дараалал буюу чиглэлтэй таарахгүй бол оролтод өгөгдсөний дагуу уг замын хөдөлгөөний хасах тэмдэгтэй хэвлэнэ үү. Тоонуудыг таслалын цэгээс хойш 5-н орны нарийвчлалтай хэвлэнэ үү.

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

Орчуулсан: Баатархүү

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

Оролт
2
3
1 2 2
1 2 4
2 1 1000
Гаралт
6.00000
2.00000
2.00000
-2.00000
Оролт
7
11
1 2 7
1 2 7
1 3 7
1 4 7
2 3 7
2 5 7
3 6 7
4 7 7
5 4 7
5 6 7
6 7 7
Гаралт
13.00000
2.00000
2.00000
3.00000
6.00000
1.00000
3.00000
4.00000
7.00000
1.00000
2.00000
6.00000
Сэтгэгдлүүдийг ачааллаж байна...