A. Бэлэг

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

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

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

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

Олимп хаант улс нь $N$ ширхэг хотууд болон $M$ ширхэг 2 урсгалтай замуудаас тогтдог. Зам болгон нь яг 2 хотыг холбох бөгөөд дурын 2 хот нь хоорондоо нэгээс илүү тооны замаар холбогдсон байж болно. Түүнчлэн зарим замууд нь ямар нэгэн хотыг өөртэй нь гогцоо үүсгэж холбосон байж болох юм.

Бүх замууд дээр дээрэмчид байнга зогсож байдаг байв. Дээрэмчид зам дээр дээрэм хийхээс уйдаж эхэлмэгцээ Олимп хаант улсын эзэн хааныг тодорхой хэмжээний мөнгө төлөхийг санал болгожээ. Тэд уг саналдаа эзэн хаанаас алт болон мөнгөн зооснуудаас тогтох бэлэг авахыг хүсэж буйгаа илэрхийлсэн байв. Мөн уг санал дотор хэсэг хязгаарлалтуудын бүртгэл агуулагдсан бөгөөд үүнд: зам болгоны хувьд тухайн зам дээрх дээрмийг зогсоохын тулд дээрэмчдэд бэлэглэх ёстой алтан зоосны хамгийн доод хэмжээ $g_{i}$ болон мөнгөн зоосны хамгийн доод хэмжээ $s_{i}$ гэсэн хязгаарлалтууд байв. Өөрөөр хэлбэл хэрэв дээрэмчдэд өгөх бэлэг нь $a$ ширхэг алтан зоос, $b$ ширхэг мөнгө зоос агуулж байвал дээрэмчид $g_{i} ≤ a$ ба $s_{i} ≤ b$ байх бүх замууд дээр дээрэм хийхээ зогсоох юм.

Харамсалтай нь эзэнт улсын эрдэнэсийн санд алтан болон мөнгөн зоос аль аль нь байхгүй бөгөөд зөвхөн Олимп хаант улсын мөнгөн дэвсгэрт болох төгрөг агуулагдаж байв. Нэг алтан зоос нь $G$ төгрөгийн үнэтэй бөгөөд нэг мөнгөн зоос нь $S$ төгрөгийн үнэтэй юм. Эзэн хаан ямар ч 2 хотын хооронд аюулгүй явж болох зам оршин байхаар дээрэмчдэд бэлэг бэлдэн илгээхийг хүсжээ. Таны даалгавар бол эзэн хааны хүслийг хангах шаардлагатай бэлгийн хамгийн бага өртгийг Олимп хаант улсын төгрөгөөр илэрхийлсэн утгыг олох юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $N$ болон $M$ ($2 ≤ N ≤ 200$, $1 ≤ M ≤ 50 000$) өгөгдөх ба эдгээр нь харгалзан хотуудын тоо болох замуудын тоог илэрхийлнэ. 2-дахь мөрөнд 2 бүхэл тоо $G$ болон $S$ ($1 ≤ G, S ≤ 10^{9}$) өгөгдөх ба эдгээр нь алтан болон мөнгөн зоосны үнийг төгрөгөөр илэрхийлсэн утга байх юм. Дараагийн $M$ мөрөнд дээрэмчдийн илгээсэн саналын тухай мэдээлэл өгөгдөнө. Уг санал доторх бүртгэлийн тэмдэглэл бүр нь 4-н бүхэл тоо $x_{i}, y_{i}, g_{i}, s_{i}$-аар өгөгдөх бөгөөд энд $x_{i}$ болон $y_{i}$ нь $i$-р замаар холбогдсон хотуудын дугаарыг илэрхийлнэ. Харин $g_{i}$, $s_{i}$ нь $i$-р замын алтан болон мөнгөн зоосны хамгийн бага шаардлагатай хэмжээнүүдийг илэрхийлнэ ($1 ≤ x_{i}, y_{i} ≤ N$, $1 ≤ g_{i}, s_{i} ≤ 10^{9}$). Хотууд нь $1$-ээс $N$ хүртэл дугаарлагдсан байна. Түүнчлэн дурын 2 хот нь хоорондоо нэгээс илүү тооны замаар холбогдсон байх боломжтой юм. Мөн ямар нэгэн хот нь өөртэйгөө замаар холбогдсон буюу гогцоо үүсгэсэн байх боломжтой.

Гаралт

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

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

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

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