Император Олимпии решил соединить \textbf{N} городов империи воздушным транспортом. Придворному программисту было приказано написать программу под названием ОлимпСтрой, которая упрощает процесс построения карты авиарейсов. Эта программа должна выполнять операции двух типов, каждая из которых зависит от трех параметров \textbf{A}, \textbf{B }и \textbf{C}: \begin{enumerate} \item Создать новый рейс из города \textbf{A }в город \textbf{B}, перелет по которому занимает \textbf{C }минут. \item Рассмотреть все авиарейсы, которые начинаются в городе \textbf{A}. Пусть рейс номер \textbf{i }из них заканчивается в городе \textbf{v_i} и занимает \textbf{t_i} минут. Для каждого такого \textbf{i }создать рейс из города \textbf{B }в город \textbf{v_i}, который занимает \textbf{t_i} + \textbf{С }минут. \end{enumerate} После выполнения всех операций программа должна для каждого города найти наименьшее время, требуемое для перелета в него из столицы, возможно с пересадками в других городах. Считается, что время посадки, высадки и ожидания в аэропорту равны нулю. Между двумя городами может быть больше одного рейса, причем перелеты по ним могут занимать разное время. Возможно существование рейсов, которые начинаются и заканчиваются в одном и том же городе. Все рейсы односторонние, то есть наличие рейса из города \textbf{A }в город \textbf{B }еще не гарантирует наличие рейса из города \textbf{B }в город \textbf{A}. Напишите программу, которая по последовательности из \textbf{M }операций описанных выше типов, выполненных программой ОлимпСтрой, для каждого города, кроме столицы, найдет наименьшее время, требуемое для перелета из столицы в этот город. \InputFile Первая строка содержит два целых числа \textbf{N }и \textbf{M }(\textbf{2 }≤ \textbf{N }≤ \textbf{10^5}, \textbf{1 }≤ \textbf{M }≤ \textbf{10^5}) - количество городов в империи Олимпия и количество операций, выполненных программой ОлимпСтрой. В каждой из следующих \textbf{M }строк содержится информация об очередной операции. Первое число в строке равно \textbf{1}, если выполняемая операция имеет первый тип, и \textbf{2}, если второй. Далее записаны три целых числа \textbf{A}, \textbf{B} и \textbf{C }(\textbf{1 }≤ \textbf{A }≤ \textbf{N}, \textbf{1 }≤ \textbf{B }≤ \textbf{N}, -\textbf{10^8} ≤ \textbf{C }≤ \textbf{10^8}), значение которых описано выше. Города нумеруются числами от \textbf{1} до \textbf{N}; столица имеет номер \textbf{1}. Гарантируется, что время перелета по каждому из рейсов будет строго положительным. \OutputFile Вывести \textbf{N - 1} строку. В \textbf{i}-й из них должно содержаться наименьшее время в минутах, за которое можно долететь из столицы в город с номером \textbf{i + 1}. Если до какого-то города добраться невозможно, выведите в соответствующей строке число \textbf{-1}.