Во время проведения очередной Межгалактической Летней Компьютерной Школы (МЛКШ) организаторы столкнулись с проблемой доставки кефирчика для вечеринки. Дело в том, что кефирчик производят на планете под номером \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}".