Хамгийн богино чиглэл I

Эхний мөрөнд $n$ ба $m$ хоёр бүхэл тоо байна: хот болон нислэгийн холбоосын тоо. Хотууд $1,2,\dots,n$ гэж дугаарлагдсан, $1$ дүгээр хот Сюрьяля.

Дараа нь нислэгийн холбоосуудыг тодорхойлсон $m$ мөр байна. Мөр бүрт $a$, $b$, $c$ гурван бүхэл тоо байна: нислэг $a$ хотоос эхэлж, $b$ хотод дуусаж, урт нь $c$. Нислэг бүр нэг чиглэлтэй.

Сюрьялягаас бусад бүх хот руу явах боломжтой гэж үзнэ.

$n$ бүхэл тоо хэвлэ: Сюрьялягаас $1,2,\dots,n$ хотууд руу хамгийн богино чиглэлийн уртууд.