Muallif: __thecrash__ 87d7c0ecdade

F. Chopar yetkazuvchi

Vaqt limiti: 2000 ms Xotira limiti: 256 mb

Qadimgi shohlikda \(n\) ta pochta bekati bor, ular \(m\) ta yo'l orqali juft-juft bog'langan (har bir yo'l ikki tomonlama, ya'ni ikkala yo'nalishda ham yurish mumkin). \(i\) - yo'ldan o'tish uchun aynan \(w_i\) soat vaqt kerak.

Chopar \(1\) - bekatdan xat olib, uni \(n\) - bekatga eltishi kerak. U bekatlar orasida istalgan yo'llar zanjiri orqali harakatlanishi mumkin (bir nechta yo'lni ketma-ket bosib o'tib). Choparning \(n\) - bekatga yetib borishi uchun ketadigan eng kam umumiy vaqtni toping. Agar chopar umuman \(n\) - bekatga yetib bora olmasa, \(-1\) chiqaring.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 \le n \le 2\times10^5\), \(0 \le m \le 4\times10^5\)) beriladi. Keyingi \(m\) ta qatorning har birida uchta butun son \(u_i, v_i, w_i\) (\(1 \le w_i \le 10^9\), \(1 \le u_i, v_i \le n\), \(u_i \neq v_i\)) beriladi — \(u_i\) va \(v_i\) bekatlar orasida o'tish \(w_i\) soat vaqt oladigan yo'l borligini bildiradi.

Chiquvchi ma'lumotlar

Yagona qatorda — choparning \(n\) - bekatga yetib borishi uchun ketadigan eng kam vaqtni (yoki \(-1\)) chiqaring.

Misollar

1

5 6
1 2 4
1 3 1
3 2 1
2 4 1
3 4 5
4 5 3

6

2

4 2
1 2 5
3 4 5

-1