A. Дотуур байрны усны хангамж

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

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

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

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

Их сургууль нийт $n$ дотуур байртай бөгөөд $1$-ээс $n$ хүртэл дугаарлагджээ. Дотуур байрны байшингуудын доогуур хоорондоо холбогдсон усны хоолойнууд байдаг байв. Хоолой бүр тодорхой чиглэл (ус зөвхөн хоолойны чиглэлийн дагуу урсана), диаметртэй (хоолойгоор боломжит хамгийн их хэмжээний ус урсана гэж үзнэ).

Байшин бүрд ус орох хоолой хамгийн ихдээ нэг, гарах хоолой хамгийн ихдээ нэг байна. Шинэ хичээлийн жил эхэлж байгаатай холбогдуулан Лулу дотуур байрандаа шинэ ус нөөцлүүр, цорго суурилуулахыг хүсч байгаа юм. Гарах урсгалтай боловч орох урсгалгүй усны хоолойтой байрнуудад нөөцлүүр, орох урсгалтай боловч гарах урсгалгүй усны хоолойтой байрнуудад цорго суурилуулах хэрэгтэй байв. Ингэснээр нөөцлүүр суурилуулсан байшингаас ус хоолойгоор дамжин цорго суурилагдсан өөр нэг байшинд очно. Өөрөөр хэлбэл усны цорго суурилуулсан байшин аль нэг усны нөөцлүүр суурилуулсан байшингаас усаа авч байх юм.

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

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $n$, $p$ гэсэн хоёр бүхэл тоо байх ба эдгээр нь харгалзан байшингуудын тоо болон усны хоолойнуудын тоо юм. $(1 ≤ n ≤ 1000, 0 ≤ p ≤ n)$

Дараагийн $p$ мөрөнд хоолойнуудын тодорхойлолтыг агуулна. $i$ дахь мөрөнд $a_{i}$, $b_{i}$, $d_{i}$ утгууд байх ба эдгээр нь $a_{i}$ дугаартай байшингаас $b_{i}$ дугаартай байшин руу явж буй хоолойны диаметрийг илтгэнэ. ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}, 1 ≤ d_{i} ≤ 10^6$)

Байшин бүрээр хамгийн ихдээ нэг хоолой орж, нэг хоолой гарна.

Гаралт

Эхний мөр $t$ гэсэн бүхэл тоо агуулах ба энэ нь хоорондоо ус дамжуулж буй нөөцлүүр суурилуулсан ба цорго суурилуулсан хос байшингуудын тоо.

Дараагийн $t$ мөрөнд мөр тус бүрт зайгаар тусгаарлагдсан $tank_{i}$, $tap_{i}$, $diameter_{i}$ гэсэн гурван бүхэл тоо хэвлэнэ. $tank_{i} ≠ tap_{i}$ ($1 ≤ i ≤ t$). Мөр бүрд байх $tank_{i}$-ын утгууд өсөх дарааллаар байрлах ёстой.

  • $tank_{i}$ - усны нөөцлүүртэй байшингийн дугаар
  • $tap_{i}$ - цорго суурилуулсан байшингийн дугаар
  • $diameter_{i}$ - дамжуулж чадах усны хамгийн их хэмжээ

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

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

Оролт
3 2
1 2 10
2 3 20
Гаралт
1
1 3 10
Оролт
3 3
1 2 20
2 3 10
3 1 5
Гаралт
0
Оролт
4 2
1 2 60
3 4 50
Гаралт
2
1 2 60
3 4 50
Сэтгэгдлүүдийг ачааллаж байна...