E. "Breaking Good" тоглоом

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

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

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

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

"Breaking Good" бол олон тоглоомчдын олж авахыг хүсдэг видео тоглоом юм. Энэ тоглоомонд туршлагатай тоглогчдод хүртэл маш хэцүү санагддаг тусгай нэгэн үе байдаг.

Волтэр Виллиам гэх тоглоомын гол дүр нь Лос Германос (Ахан дүүс) гэх бүлгэмд орохыг хүсдэг. Энэ бүлгэм бүхэл бүтэн улсыг хяналтандаа байлгаж чаддаг юм. Энэ улс нь $n$ ширхэг хотоос бүрддэг бөгөөд $m$ ширхэг зам тэдгээрийг холбож байдаг. Үүнд хот нь өөртэйгөө холбосон зам байхгүй бөгөөд аль ч хоёр хотын хооронд хамгийн ихдээ нэг л зам байх юм. Аль ч хотоос замуудыг ашиглан ямар ч хот уруу очиж болох юм.

Замууд одоогоор бүрэн ажиллахгүй байлаа. Зарим замуудыг ажилд оруулахын тулд засвар хийх хэрэгтэй.

Бүлгэм банк дээрэмдэх гэж байна. Банк нь $1$-р хотод байрладаг. Дээрэмдэх үйл ажиллагаа тэдний хувьд гаршсан зүйл боловч хэцүү хэсэг нь банкнаас төв байр луугаа зугтан гарах байлаа. Бүлгэмийн төв байр нь $n$-р хотод байрладаг. Бүлгэмийн итгэлийг олж авахын тулд Волтэр энэ ажиллагааг хийхээр болсон бөгөөд тэр ухаалаг төлөвлөгөө бодож оллоо.

Юу түрүүнд тэдний явах $1$-р хотоос төв байр болох $n$ хот уруу явах зам нь хамгийн богино байх ёстой. Учир нь ажиллагааг хамгийн бага хугацаанд хийх нь чухал.

Дараа нь бүлгэм энэ замаас бусад замуудыг дэлбэлнэ. Учир нь цагдаа нарын нэмэлт хүч ирэхээс сэргийлэх юм. Ажилладаггүй замуудын хувьд тэдгээрийг дэлбэлэх шаардлагагүй.

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

Хамгийн богино байж болох замууд олон байсан болохоор өөрчлөх замууд буюу дэлбэлэх бас засварлах шаардлагатай замуудыг хамгийн бага тоотой байхаар сонгожээ.

Та Волтэрийг даалгаварыг нь гүйцэтгэж бүлгэмийн итгэлийг олоход нь тусалж чадах уу?

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n, m$ $(2 ≤ n ≤ 10^{5}; 0 ≤ m ≤ min(\frac{n(n-1)}{2}, 10)$ байна. Энэ нь харгалзан хотын тоо болон замын тоо болно.

Дараагийн $m$ ширхэг мөрөнд замуудын тайлбарууд. Тайлбар болгон гурван ширхэг $x, y, z$ ($1 ≤ x, y ≤ n; z \in (0, 1))$ бүхэл тооноос бүрдэнэ. Энэ зам нь $x$ болон $y$-р хотуудыг хооронд нь холбосон замыг илэрхийлнэ. Хэрвээ $z = 1$ бол энэ зам ажиллаж байгаа үгүй бол ажиллахгүй байгаа.

Гаралт

Эхний мөрөнд бүлгэмийн дэлбэлэх юмуу засах ёстой замын хамгийн бага $k$ тоог хэвлэнэ.

Дараагийн $k$ мөрөнд мөр бүрд өөрчлөх ёстой замыг илэрхийлэх гурван бүхэл $x, y, z$ ($1 ≤ x, y ≤ n; z \in (0, 1)$ тоог хэвлэнэ. $z = 1$ бол $x$ болон $y$-р хотуудыг холбосон зам засагдах ёстой. $z = 0$ бол замыг дэлбэлэх ёстой.

Замуудыг ямар ч дараалалтайгаар хэвлэж болно. Өөрчлөгдсөн зам болгон нэг удаа хэвлэгдэнэ. Нэг замаар холбогдсон хотуудыг ямар ч дараалалтайгаар хэвлэж болно. Хэвлэгдсэн замын бүрийн анхын төлөв буюу $z$ утга өөрчлөгдсөн байх ёстой.

Бүх ажиллагааг хийж гүйцэтгэсний дараа $1$ болон $n$-р хотын хоорондох хамгийн богино зам дээр ажиллагаа явагдана.

Хэрвээ боломжит оновчтой олон хариулт байвал аль нэгийг нь хэвлээрэй.

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

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

Оролт
2 1
1 2 0
Гаралт
1
1 2 1
Оролт
4 4
1 2 1
1 3 0
2 3 1
3 4 1
Гаралт
3
1 2 0
1 3 1
2 3 0
Оролт
8 9
1 2 0
8 3 0
2 3 1
1 4 1
8 7 0
1 5 1
4 6 1
5 7 0
6 8 0
Гаралт
3
2 3 0
1 5 0
6 8 1

Тэмдэглэл

Эхний жишээнд зөвхөн $1 - 2$ гэсэн зам бий.

Хоёр дахь жишээнд хамгийн богино зам нь $1 - 3 - 4$.

Гурав дахь жишээнд олон богино зам бий гэхдээ хамгийн оновчтой нь $1 - 4 - 6 - 8$

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