Таньд жинтэй чиглэлгүй граф өгөгджээ. Таны даалгавар өгөгдсөн графын хувьд $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$ гэж хэвлэнэ үү?