C. Dijkstra?

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

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

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

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

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

Оролт

Эхний мөрөнд $n$ ба $m$ ($2 ≤ n ≤ 10^5; 0 ≤ m ≤ 10^5$). Энд $n$ нь оройн тоо ба $m$ нь ирмэгийн тоо.

Дараагийн $m$ мөрөнд $a_i$, $b_i$ ба $w_i$ ($1 ≤ a_i, b_i ≤ n; 1 ≤ w_i ≤ 10^6$) $a_i$ ба $b_i$ ирмэгүүд хоорондоо $w_i$ жинтэй ирмэгээр холбогдсоныг илэрхийлсэн тоонууд өгөгдөнө.

Гаралт

$1$-р оройгоос $n$-р оройд хүрэх зам олддог бол $1$-р оройгоос $n$-р оройд хүрэх замд таарах оройн дугааруудыг хэвлэнэ үү?

Энэ бодлого олон хариутай тул аль нэг хариуг хэвлэхэд болно. Хэрэв боломжгүй бол $-1$ гэж хэвлэнэ үү?

Орчуулсан: Адъяа

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

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