D. Хүргэлтийн баавгайнууд

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

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

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

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

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

Хотод Нивел баавгайнуудын бараа хүргэлтийг зохицуулах ажилд оржээ.Түүний амьдарч буй хот нь $n$ ширхэг зангилааны цэг болон $m$ ширхэг ирмэгтэй чиглэлтэй графаар дүрслэгдэнэ. Ирмэг бүр нь жингийн багтаамжтай юм.Хүргэлт нь $1$-дэх зангилааны цэгээс $n$-дэх зангилааны цэг хүртэлх энгийн зам дээр баавгайн өөрийн гараараа зөөж буй жингүүдээс тогтоно.Тухайн ирмэгээр туулсан нийт жингийн хэмжээ нь заавал тухайн ирмэгийн жингийн багтаамжаас хэтрэхгүй байх юм.

Нивел-д яг $x$ ширхэг баавгай байв.Шударга байлгах үүднээс, ямар ч баавгай амрахгүй ба баавгай бүрийн зөөсөн жин нь яг ижил байх ёстой.Гэхдээ, хэрэв тэд дуртай байвал баавгай бүр нь өөр замаар явж болно.

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

Оролт

Эхний мөрөнд харгалзан зангилааны цэгийн тоо, чиглэлтэй ирмэгийн тоо болон баавгайн тоог илэрхийлэх 3-н бүхэл тоо $n$, $m$ болон $x$ ($2 ≤ n ≤ 50$, $1 ≤ m ≤ 500$, $1 ≤ x ≤ 100 000$) өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд 3-н бүхэл тоо $a_{i}$, $b_{i}$ and $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$, $1 ≤ c_{i} ≤ 1 000 000$) өгөгдөнө.Энэ нь $a_{i}$ зангилааны цэгээс $b_{i}$ зангилааны цэг хүртэлх $c_{i}$ жингийн багтаамжтай чиглэлтэй ирмэгийг илэрхийлэх юм.Ямар ч өөртөө хийх гогцоо байхгүй ба нэг хотоос бусад хот хүртэл олон тооны ирмэг байхгүй юм. Илүү албан ёсоор хэлэхэд, $i ≠ j$ байх $i$ болон $j$ бүрийн хувьд $a_{i} ≠ a_{j}$ эсвэл $b_{i} ≠ b_{j}$ байх юм.Мөн $1$-дэх зангилааны цэгээс $n$-дэх зангилааны цэг хүртэл дор хаяж нэг зам байна.

Гаралт

Дан мөрөнд нэг бодит утга хэвлэнэ -- энэ нь хэрэв Нивел яг $x$ ширхэг баавгай ашиглахад түүний хүргэж чадах жингийн хамгийн их хэмжээг илэрхийлнэ.Таны хариулт нь хэрэв үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-аас хэтрэхгүй бол зөвөөр тооцогдоно.

Тухайлбал: Таны хариултыг $a$-аар тэмдэглэх ба шүүх хариултыг $b$-ээр тэмдэглэе.Шалгагч программ нь хэрэв if байвал таны хариултыг зөвөөр тооцох юм.

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

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

Оролт
4 4 3
1 2 2
2 4 1
1 3 1
3 4 2
Гаралт
1.5000000000
Оролт
5 11 23
1 2 3
2 3 4
3 4 5
4 5 6
1 3 4
2 4 5
3 5 6
1 4 2
2 5 3
1 5 2
3 2 30
Гаралт
10.2222222222

Тэмдэглэл

Эхний жишээнд, Нивелд 3-н баавгай байна. 2 баавгай нь замыг сонгож болох ба 1 баавгай нь замыг сонгож болно. замаар явах баавгай нь 1 нэгж жин зөөж чадах хэдий ч, шударга байлгах үүднээс тэрээр 0.5 нэгж жин зөөхөөр хязгаарлагдана. Түүнчлэн, нийт жин нь 1.5 нэгж болно. Нивел 2 баавгайгаар л илүү их жин зөөж чадах байсан ч тэрээр энэ өдөр заавал 3-н баавгайг ашиглах ёстойг анхаарна уу.

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