Під час проведення чергової Міжгалактичної Літньої Комп'ютерної Школи (МЛКШ) організатори зіткнулись з проблемою доставки кефірчика для вечірки. Справа у тому, что кефірчик виробляють на планеті під номером \textbf{1}, а самі школярі живуть на планеті \textbf{n}, тому на доставку кефірчика витрачається досить великий час, а значить він встигає зіпсуватись. На щастя, галактична транспортна система "Берендєєв-Експрес" поступово впроваджує нові кефіропроводи, здатні передавати кефір зі швидкістю, яка у два рази перевищує швидкість старих моделей. А саме, з довільної планети на довільну по старим кефіропроводам кефір проходить за два роки, а по новим - за один. Зрозуміло, грішно було б не скористатисья інноваційними технологіями, тому директор МЛКШ попросив вас написати програму, яка за даними про наявні кефіропроводи (як нові, так і старі) взнає найшвидший шлях від планети \textbf{1} до планети \textbf{n}. \InputFile У першому рядку вхідного файлу задано два цілих числа \textbf{n} та \textbf{m} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}, \textbf{0} ≤ \textbf{m} ≤ \textbf{100000}) - кількість планет та кількість кефіропроводів відповідно. У наступних \textbf{m} рядках задано трійки натуральних чисел \textbf{u_i}, \textbf{v_i} та \textbf{c_i}. Числа \textbf{u_i} та \textbf{v_i} позначають номери планет, з'єднаних \textbf{i}-м кефіропроводом, а \textbf{c_i} (\textbf{c_i=1} або \textbf{c_i=2}) - кількість років, які буде потрібно, щоб передати кефір з однієї планети на іншу через \textbf{i}-й кефіропровод. Планети у вхідному файлі нумеруються з одиниці. Кефір по трубопроводам можна передавати в обох напрямках. \OutputFile У вихідний файл потрібно вивести одне число - кількість років, які знадобиться, щоб доставити кефір з планети \textbf{1} на планету \textbf{n}. Якщо доставка неможлива, то у вихідний файл потрібно вивести "\textbf{-1}".