G. Шар айрагны төлөө гүй

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

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

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

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

БабблЛандын хүмүүс шар айраг уух дуртай. Эндэхийн шар айраг нь их сайн, хүчтэй учраас та үүнийг уух болгондоо таны хурд уухаасаа өмнөх үеийн хурднаас 10 дахин удаан болдог.

Бирко Бийрград хотод амьдардаг ба Бийрбүрг хот руу явахыг хүсчээ. Танд БабблЛандын замын газрын зураг өгөгдсөн ба та түүнд хамгийн хурдан замыг олж өгөх хэрэгтэй. Тэр аялалаа эхлэхээс өмнө түүний хурд 1 байна. Шинэ хотод ирэх болгондоо тэр нутгийн шар айрагнаас нэг аягийг уудаг ба энэ нь түүний хурдыг 10 дахин удаашруулдаг.

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

Бийрградаас Бийрбүрг хүртэл зам олдох нь батлагдсан.

Оролт

Оролтын эхний мөр БабблЛанд дах хотын тоог заах бүхэл тоо $N$, замын тоог заах бүхэл тоо $M$-г агуулна. Хотууд нь 0-ээс $N - 1$ хооронд дугаарлагдсан ба 0-р хот нь Бийрград, $N - 1$-р хот нь Бийрбүрг хот байна.

Дараагийн $M$ мөр бүр $a$, $b$ ($a ≠ b$) ба $len$ гэсэн тоонууд агуулна. Энэ тоонууд нь $a$ ба $b$ хотын хооронд $len$ урттай хоёр чиглэлтэй зам байна гэдгийг илтгэж байна.

  • $2 ≤ N ≤ 10^{5}$
  • $1 ≤ M ≤ 10^{5}$
  • $0 ≤ len ≤ 9$
  • 2 хотын хооронд хамгийн ихдээ 1 зам л байна.

Гаралт

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

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

Гуравдугаар мөрөнд энэ замд байгаа хотуудын дугаарыг очих дарааллын дагуу хоосон зайгаар тусгаарлан агуулсан байх ёстой.

Орчуулсан: Жавхлан

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

Оролт
8 10
0 1 1
1 2 5
2 7 6
0 3 2
3 7 3
0 4 0
4 5 0
5 7 2
0 6 0
6 7 7
Гаралт
32
3
0 3 7
Сэтгэгдлүүдийг ачааллаж байна...