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