Viloyatda $n$ ta shahar va ularni tutashtiruvchi $m$ ta ikki tomonlama yo‘l bor, har bir yo‘lning uzunligi ma’lum. 1-shahardan $n$-shaharga eng qisqa yo‘l uzunligini toping.
Kirish ma‘lumotlari
Birinchi qatorda $n$ va $m$ ($2 \le n \le 10^5$, $0 \le m \le 10^5$). Keyingi $m$ ta qatorda $u$, $v$, $w$ — $u$ va $v$ shaharlar orasidagi yo‘l uzunligi ($1 \le u, v \le n$, $1 \le w \le 10^6$). Bir juft shahar orasida bir nechta yo‘l, shahardan o‘ziga yo‘l bo‘lishi mumkin.
Chiqish ma‘lumotlari
Eng qisqa yo‘l uzunligi; $n$-shaharga borib bo‘lmasa, -1.
Misollar
Kirish
4 5 1 2 4 1 3 1 3 2 2 2 4 5 3 4 9
Chiqish
8
Kirish
3 1 1 2 5
Chiqish
-1