Доставка кефирчика
Доставка кефирчика
Во время проведения очередной Межгалактической Летней Компьютерной Школы (МЛКШ) организаторы столкнулись с проблемой доставки кефирчика для вечеринки. Дело в том, что кефирчик производят на планете под номером 1, а сами школьники живут на планете n, поэтому на доставку кефирчика тратится довольно большое время, а значит он успевает испортиться.
К счастью, галактическая транспортная система "Берендеев-Экспресс" постепенно внедряет новые кефиропроводы, способные передавать кефир со скоростью, в два раза превышающей скорость старых моделей. А именно, с любой планеты на любую по старым кефиропроводам кефир проходит за два года, а по новым - за один.
Разумеется, грешно было бы не воспользоваться инновационными технологиями, поэтому директор МЛКШ попросил вас написать программу, которая по данным о имеющихся кефиропроводах (как новых, так и старых) узнает кратчайший путь от планеты 1 до планеты n.
Giriş verilənləri
В первой строке входного файла даны два целых числа n и m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 100000) - количество планет и количество кефиропроводов соответственно. В последующих m строках даны тройки натуральных чисел ui,vi и ci. Числа ui и vi обозначают номера планет, соединённых i-м кефиропроводом, а ci (ci=1 или ci=2) - количество лет, которое потребуется, чтобы передать кефир с одной планеты на другую через i-й кефиропровод. Планеты во входном файле нумеруются с единицы. Кефир по трубопроводам можно передавать в обоих направлениях.
Çıxış verilənləri
В выходной файл требуется вывести одно число - количество лет, которое требуется, чтобы доставить кефир с планеты 1 на планету n. Если доставка невозможна, то в выходной файл требуется вывести "-1".
Nümunə
3 2 1 2 2 2 3 1
3