H. Том Марафон

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

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

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

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

Берланд-ын тусгаар тогтнолын өдрөөр нэгэн том марафон уралдаан зохион байгуулахаар болжээ. Берланд $n$ ширхэг хотоос тогтох бөгөөд зарим хотууд нь хоорондоо 2 урсгалтай замаар холбогдсон байв. Зам болгон нь тодорхой урттай бөгөөд хотууд нь 1-ээс $n$ хүртэл дугаарлагдсан байх юм. Түүнчлэн хотын ямар ч хотоос бусад ямар ч хот уруу эдгээр замуудыг ашиглан хүрч болох ажээ.

$n$ ширхэг гүйгч уралдаанд оролцох бөгөөд хот болгоноос нэг гүйгч оролцож байв. Берландын гүйгчид нь төрөлхийн чалчаа учраас шүүгчид марафон уралдаанд оролцогчдын тоог хэт олон байлгахаас ийнхүү зайлсхийжээ. Шүүгчид гүйгч болгоныг өөрийн хотоос эхэлж гүйхээр шийдсэн бөгөөд уралдаан эхлэхээс өмнө гүйгч болгон нь тухайн гүйгч уралдаанаа дуусгах ёстой хотын нэрийг бичсэн цаас авсан байх юм. Гүйгч бүрийн хувьд барианы хот нь дурын байдлаар сонгогдсон байх боловч уг хот нь гарааны хоттой давхацсан байж болохгүй ажээ. Мөн хэд хэдэн гүйгчид нь нэг ижил хотод уралдаанаа дуусгаж болно. Бүх гүйгчид нь нэгэн зэрэг уралдаанаа эхлүүлэх ба хүн болгон гарааны цэгээс барианы цэг хүртэлх хамгийн богино замыг туулан гүйх юм. Түүнчлэн бүх гүйгчид нь ижилхэн $1$ гэсэн хурдаар гүйнэ.

Тэмцээний дараа онооны хүснэгтийг хийх бөгөөд энд гүйгчид нь өөрсдийн уралдааны замаа туулсан хугацаануудын үл буурах дарааллын дагуу эрэмбэлэгдсэн байх юм. Уг хүснэгтийн эхний $g$ ширхэг гүйгч алтан медаль хүртэх ба дараагийн $s$ ширхэг гүйгч мөнгөн медаль хүртэх бөгөөд үлдсэн бүх гүйгчид нь хүрэл медаль хүртэх ажээ. Түүнчлэн хэрэв 2 болон түүнээс олон тооны гүйгчид яг ижил хугацааг уралдааны замаа туулахад зарцуулсан байвал тэд уралдаан эхлүүлсэн хотуудынхаа дугааруудын өсөх дарааллын дагуу эрэмбэлэгдэнэ. Иймд ямар ч 2 гүйгч нь ижил байр эзлэхгүй байх юм.

Уг уралдааны дүрмийн дагуу алтан медалийн тоо $g$ нь заавал $g_{1} ≤ g ≤ g_{2}$ гэсэн тэнцэтгэл бишийг хангах ёстой бөгөөд энд $g_{1}$ болон $g_{2}$ нь түүхийн явцад үүссэн утгуудыг илэрхийлнэ. Мөн ижлээр мөнгөн медалийн тоо $s$ нь заавал $s_{1} ≤ s ≤ s_{2}$ гэсэн тэнцэтгэл бишийг хангах ёстой бөгөөд энд $s_{1}$ болон $s_{2}$ нь түүхийн явцад үүссэн утгуудыг илэрхийлэх юм.

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

Оролт

Оролтын эхний мөрөнд бүхэл тоонууд $n$ болон $m$ ($3 ≤ n ≤ 50$, $n - 1 ≤ m ≤ 1000$) өгөгдөх ба энд $n$ нь Берландын хотуудын тоог, $m$ нь замуудын тоог илэрхийлнэ.

Дараагийн $m$ мөрөнд замуудын тайлбар өгөгдөх бөгөөд тайлбар тус бүр нь 3-н бүхэл тоо $v$, $u$, $c$-ээр өгөгдөх ба эдгээр нь уг замаар холбогдож буй хотуудын дугаарууд болон уг замын уртыг тус тус илэрхийлнэ ($1 ≤ v, u ≤ n$, $v ≠ u$, $1 ≤ c ≤ 1000$). Хос хотууд болгоны хооронд нэгээс ихгүй зам байх юм.

Сүүлийн мөрөнд бүхэл тоонууд $g_{1}$, $g_{2}$, $s_{1}$, $s_{2}$ ($1 ≤ g_{1} ≤ g_{2}$, $1 ≤ s_{1} ≤ s_{2}$, $g_{2} + s_{2} < n$)-ууд өгөгдөнө. Оролтын нэг мөрөнд байрлах тоонууд нь зайгаар тусгаарлагдсан байна.

Гаралт

Медаль олгох нийт аргын тоог илэрхийлэх ганц тоог хэвлэнэ үү. Мөн уг хариу нь стандарт тэмдэгт 64-бит өгөгдлийн төрөлд тохирсон байна.

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

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

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