Імператор Олімпії вирішив з’єднати \textbf{N} міст імперії повітряним транспортом. Придворному програмісту було наказано написати програму під назвою \textit{ОлімпБуд}, яка спрощує процес побудови карти авіарейсів. Ця програма має виконувати операції двох типів, кожна з яких залежить від трьох параметрів \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} операцій описаних вище типів, виконаних програмою \textit{ОлімпБуд}, для кожного міста, окрім столиці, знайде найменший час, що потрібен для перельоту зі столиці до цього міста. \InputFile Перший рядок містить два цілих числа \textbf{N }і \textbf{M }(\textbf{2 }≤ \textbf{N }≤ \textbf{10^5}, \textbf{1 }≤ \textbf{M }≤ \textbf{10^5}) - кількість міст в імперії Олімпія та кількість операцій, виконаних програмою \textit{ОлімпБуд}. У кожному з наступних \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}. Гарантується, що час перельоту по кожному з рейсів буде \textit{строго додатним}. \OutputFile Вивести \textbf{N - 1} рядок. У \textbf{i}-му з них має міститись найменший час у хвилинах, за який можна долетіти зі столиці у місто з номером \textbf{i + 1}. Якщо до якогось міста дістатись неможливо, то виведіть у відповідному рядку число \textbf{-1}.