E. Зам засвар

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

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

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

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

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

Яг одоо Берландын хөрш улс дайнаар сүрдүүлж байгаа. Иймд Берландын засгийн газрынхан хот бүр рүү цэргийн салаа явуулахаар шийдсэн. Цэргийн салаа зөвхөн ашиглагдаж байгаа замын дагуу л явж чадах ба шинэ зам барих цаг болон мөнгө байхгүй. Гэсэн хэдий ч зарим хотуудад хүрэхийн тулд зарим замуудыг засч болно.

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

Оролт

Эхний мөрөнд хотуудын тоо, замуудын тоо болох $n$, $m$ тоонууд зайгаар тусгаарлагдан өгөгдөнө. $(1 ≤ n, m ≤ 10^{5})$

Дараагийн $m$ мөрөнд мөр тус бүрд зайгаар тусгаарлагдсан гурван бүхэл тоон утга байна: $a_{i}, b_{i}, c_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, 0 ≤ c_{i} ≤ 1)$. Эдгээр нь $a_{i}$ хотоос $b_{i}$ хот хүртэлх замыг тодорхойлох ба хэрвээ $c_{i}$ нь $0$-тэй тэнцүү байвал энэ зам сайн зам гэсэн үг. Харин $1$-тэй тэнцүү бол энэ зам засагдах хэрэгтэй гэсэн үг.

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

Гаралт

Хэрвээ бүх зам засагдсан ч нийслэлээс зарим хот руу очих боломжгүй байвал "-1" гэж хэвлэнэ.

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

Засах шаардлагатай замын боломжит тооны олон хувилбар байвал алийг нь ч хэвлэсэн болно. Хэрвээ оролтонд өгсөн өгөгдлөөс бүх хот руу хүрч чадаж байвал гаралтанд зөвхөн $0$-ийг хэвлээрэй.

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

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

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

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