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