E. Төмөр Хүн

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

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

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

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

Тони Старк өөрийн өмсгөлүүдтэйгээ (одоо эдгээр өмсгөлүүд нь автомат нисгэгчтэй болсон ) тоглоом тоглож байв. Тэрээр Малибу-д амьдарч байгаа ба Малибу-д $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг замын уулзварууд болон $n - 1$ ширхэг хоорондоо холбогдсон замууд байдаг ажээ. Та ямар нэгэн уулзвараас бусад ямар ч уулзвар уруу эдгээр замуудыг ашиглан хүрч болох юм. Өөрөөр хэлбэл Малибу-ын граф нь мод үүсгэнэ.

Тони-д $m$ ширхэг өмсгөл байдаг бөгөөд өмсгөл болгон нь өөрийн гэсэн тусгай төлөвлөгөөтэй байв. $i$-дахь өмсгөл нь хугацааны $t_{i}$ гэсэн мөчид $v_{i}$ гэсэн уулзвар дээр гарч ирэх бөгөөд $u_{i}$ гэсэн уулзвар уруу $v_{i}$ болон $u_{i}$-ын хоорондох хамгийн богино маршрутын дагуу секундэд $c_{i}$ ширхэг зам туулж байхаар хөдлөх ба (уулзварыг өнгөрөхөд ямар нэгэн хугацаа зарцуулахгүй гэж үзнэ) $u_{i}$ уулзвар дээр очмогцоо маш хурдан алга болох юм. Хэрэв өмсгөл нь $u_{i}$ дээр $q$ хугацаанд очвол тэрээр тухайн уулзвар дээр хугацааны $q$ гэсэн мөчид байх бөгөөд үүнээс цааш хугацааны мөчид тэрээр тухайн уулзвар дээр байхгүй байна гэж үзэх юм. Түүнчлэн өмсгөл нь тасралтгүй хөдлөх ба жишээлбэл хэрэв $v_{i} ≠ u_{i}$ байвал хугацааны гэсэн мөчид өмсгөл нь нэгэн замын яг дунд байх юм. Хэрэв $v_{i} = u_{i}$ байвал энэ нь өмсгөл нь $v_{i}$ гэсэн уулзвар дээр хугацааны $t_{i}$ гэсэн мөчид байх бөгөөд үүний дараа шууд алга болохыг анхаарна уу.

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

Таны даалгавар бол хэрэв ямар нэгэн дэлбэрэлт үүсэх бол Тони-д хамгийн эхний дэлбэрэлт болох хугацааны мөчийг хэлж өгөх юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 100 000$) өгөгдөх ба эдгээр нь харгалзана замын уулзваруудын тоо болон өмсгөлүүдийн тоог илэрхийлнэ.

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

Дараагийн $m$ мөрөнд өмсгөлүүдийн тайлбар өгөгдөнө. Эдгээр мөрүүдийн $i$-дахь мөрөнд 4 ширхэг бүхэл тоо $t_{i}$, $c_{i}$, $v_{i}$ болон $u_{i}$ ($0 ≤ t_{i} ≤ 10 000, 1 ≤ c_{i} ≤ 10 000$, $1 ≤ v_{i}, u_{i} ≤ n$) өгөгдөх ба эдгээр нь $i$-дахь өмсгөл нь хугацааны $t_{i}$ гэсэн мөчид $v_{i}$ гэсэн уулзвар дээр гарч ирэх бөгөөд $u_{i}$ гэсэн уулзвар уруу секундэд $c_{i}$ ширхэг зам туулж байхаар хөдөлнө гэдгийг илэрхийлэх юм.

Гаралт

Хэрэв ямар ч дэлбэрэлт болохгүй бол гаралтын эхний мөрөнд -1 гэж хэвлэнэ үү.

Бусад тохиолдолд хамгийн эхний дэлбэрэлт болох хугацааны мөчийг хэвлэнэ үү.

Хэрэв таны хариултын харьцангуй болон абсолют алдаа нь $10^{ - 6}$-аас хэтрэхгүй бол зөвөөр тооцогдоно.

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

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

Оролт
6 4
2 5
6 5
3 6
4 6
4 1
27 6 1 3
9 5 1 6
27 4 3 4
11 29 2 6
Гаралт
27.3
Оролт
6 4
3 1
4 5
6 4
6 1
2 6
16 4 4 5
13 20 6 2
3 16 4 5
28 5 3 5
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...