B. Инээдмийн байшин

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

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

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

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

Инээдмийн байшин нь хүнд урам зориг оруулахын тулд бүтээгдсэн. Түүний зарим өрөөнүүд нь хаалгаар холбогдсон байдаг. Петя холбогдсон өрөө бүрийн $c_{ij}$-ийг мэдэж байгаа. $c_{ij}$ нь $i$ дугаар өрөөнөөс $j$ дүгээр өрөө рүү ороход хүний урам зориг хэдээр нэмэгдэхийг илэрхийлнэ.

Петя тодорхой тойрог замаар явснаар хүний урамыг хязгааргүй нэмэгдүүлж болох эсэхийг мэдэхийг хүсжээ. Хэрэв боломжтой бол тэр тойрог нь хамгийн багадаа хэдэн өрөөнөөс бүтэхийг мэдэхийг хүсэв.

Оролт

Эхний мөрөнд байшинд хэдэн өрөө байгааг илтгэх $n$ тоо болон хэдэн хаалга байгаа илэрхийлэх $m$ enter image description here тоо өгөгдөнө. Дараагийн $m$ мөр бүрт $i$, $j$, $c_{ij}$ болон $c_{ji}$ ($1 ≤ i, j ≤ n, i ≠ j,  - 10^4 ≤ c_{ij}, c_{ji} ≤ 10^4$) тоонууд өгөгдөнө. 2 өрөөг хамгийн ихдээ нэг л хаалга холбоно мөн хаалга нь өрөөг өөртэй нь холбохгүй.

Гаралт

Хүний урмыг хязгааргүй нэмэгдүүлэх хамгийн бага урттай тойрогын урт. Хэрэв ийм тойрог олдохгүй бол $0$-ийг хэвлэ.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

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

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

Оролт
4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3
Гаралт
4

Тэмдэглэл

Cycle is such a sequence of rooms $a_{1}$, $a_{2}$, ..., $a_{k}$, that $a_{1}$ is connected with $a_{2}$, $a_{2}$ is connected with $a_{3}$, ..., $a_{k - 1}$ is connected with $a_{k}$, $a_{k}$ is connected with $a_{1}$. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as $k$, the sequence's length. Note that the minimum possible length equals two.

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