B. Гаригууд

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

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

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

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

Гоаулд Апосис Жэк Онилийн багийг дахин олзлосон! Жэк өөрөө зугтах боломжтой байв гэхдээ энэ үед Апописийн хөлөг гипер орон зайд ниссэн. Гэхдээ Жэк Апописийн газардах гаригийг мэдэж байна. Найзуудыгаа аврахын тулд Жэк ахин дахин сансрын гүүрээр явж уг гаригт очих ёстой.

Галагтик нийтдээ $n$ гаригтай ба $1$-c $n$ хүртэл дугаарлагдсан. Жэк 1 дугаартай гариг дээр байна, мөн Апопис $n$ дугаартай гариг дээр газардана. Жэк сансрын гүүрийг ашиглан хоёр гаригийн хооронд шилжиж чадна (тэр хоёр чиглэлд шилжиж чадна); ялгаатай хос хотуудын хооронд шилжих нь ялгаатай хугацаа зарцуулна. Жэк аялалаа хугацааны 0 агшинд эхлүүлнэ.

Жэкийн байрлаж буй гаригт өөр аялагчид ирж болно. Энэ тохиолдолд Жэк сансрын гүүрийг ашиглахаасаа өмнө яг 1 секунд хүлээх хэрэгтэй. Энэ нь хэрвээ хугацааны $t$ агшинд гариг дээр өөр аялагч ирвэл Жэк $t + 1$ агшинд сансрын гүүрийг ашиглах боломжтой болох юм гэхдээ $t + 1$ агшинд уг гариг дээр өөр аялагч ирж байх ёсгүй.

Гаригууд хооронд шилжих хугацаа болон Жэкийн тухайн гариг дээр сансрын гүүр ашиглах боломжгүй үеүд мэдэгдэж байгаа бол $n$ дугаартай гариг дээр очиж чадах хамгийн бага хугацааг тодорхойлно уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) буюу галактик дахь гаригуудын тоо болон $m$ ($0 ≤ m ≤ 10^{5}$) буюу Жэкийн сансрын гүүрийг ашиглаж болох гаригийн хослолуудын тоо байна. Дараагийн $m$ мөр бүрт гурван бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) буюу сансрын гүүрээр холбогдсон гаригуудын дугаар ба эдгээр гаригуудын хооронд шилжих хугацааг илэрхийлэх $c_{i}$ ($1 ≤ c_{i} ≤ 10^{4}$) бүхэл тоо байна. Дурын хоёр хотын хооронд хамгийн ихдээ нэг сансрын гүүр бүхий холболт байна.

Дараагийн $n$ мөрийн $i$-р мөрөнд бүхэл тоо $k_{i}$ ($0 ≤ k_{i} ≤ 10^{5}$) байх ба энэ нь $i$ дугаартай гариг дээр өөр аялагчид ирэх хугцаануудын тоог илэрхийлнэ. Тэгээд зайгаар тусгаарлагдсан $k_{i}$ ялгаатай бүхэл тоо $t_{ij}$ ($0 ≤ t_{ij} < 10^{9}$) байх ба өсөх эрэмбээр эрэмбэлэгдсэн байна. $t_{ij}$ бүхэл тоо нь хугацааны $t_{ij}$ агшинд (секундээр) $i$ гариг дээр өөр аялагч ирнэ гэдгийг илэрхийлнэ. Бүх $k_{i}$ тоонуудын нийлбэр $10^{5}$-с хэтрэхгүй.

Гаралт

Жэк 1 дугаартай гаригаас $n$ дугаартай гаригт очиход шаардлагатай хугацааны хамгийн бага хэмжээг илэрхийлэх нэг тоог хэвлэ. Хэрвээ Жэк ямар ч хугацаанд $n$ дугаартай гаригт очих боломжгүй бол -1 гэж хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
Гаралт
7
Оролт
3 1
1 2 3
0
1 3
0
Гаралт
-1

Тэмдэглэл

Эхний жишээн дээр Жэк 1 дугаартай гаригаас явах гурван зам байна. Хэрвээ тэр 4 дугаартай гаригруу явбал 8 секунд зарцуулна. Хэрвээ тэр 3 дугаартай гаригруу явбал 3 секунд зарцуулах боловч 3 гариг дээр хугацааны 3 болон 4 агшинд аялагчид ирэх учир Жэк 4 дугаартай гариг руу 5 агшинд явах боломжтой ба нийтдээ 8 секунд зарцуулна. Гэхдээ Жэк 2 дугаартай гаригруу яваад дараа нь 4 дугаартай гаригт очвол нийтдээ $2 + 5 = 7$ секунд зарцуулна.

Хоёр дахь жишээн дээр Жэк сансрын гүүрнүүдийг ашиглан 1 дугаартай гаригаас 3 дугаартай гаригт очих боломжгүй.

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