Імператор Олімпії вирішив з’єднати N міст імперії повітряним транспортом. Придворному програмісту було наказано написати програму під назвою ОлімпБуд, яка спрощує процес побудови карти авіарейсів. Ця програма має виконувати операції двох типів, кожна з яких залежить від трьох параметрів A, B і C:
Створити новий рейс з міста A до міста B, переліт по якому триває C хвилин.
Розглянути всі авіарейси, які починаються в місті A. Нехай рейс номер i з них закінчується у місті v_i та триває t_i хвилин. Для кожного такого i створити рейс з міста B до міста v_i, який триває t_i + С хвилин.
Після виконання всіх операцій програма має для кожного міста знайти найменший час, потрібний для перельоту до нього зі столиці, можливо з пересадками в інших містах. Вважається, що час посадки, висадки та очікування в аеропорту рівний нулю.
Між двома містами може бути більше одного рейсу, причому перельоти по них можуть займати різну кількість часу. Можливе існування рейсів, які починаються і закінчуються в одному і тому самому місті. Всі рейси односторонні, тобто наявність прямого рейсу з міста A до міста B ще не гарантує, що існує прямий рейс з міста B до міста A.
Напишіть програму, яка за послідовністю з M операцій описаних вище типів, виконаних програмою ОлімпБуд, для кожного міста, окрім столиці, знайде найменший час, що потрібен для перельоту зі столиці до цього міста.
Перший рядок містить два цілих числа N і M (2 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5) - кількість міст в імперії Олімпія та кількість операцій, виконаних програмою ОлімпБуд. У кожному з наступних M рядків міститься інформація про чергову операцію. Перше число в рядку рівне 1, якщо виконувана операція має перший тип, і 2, якщо другий. Далі записані три цілих числа A, B та C (1 ≤ A ≤ N, 1 ≤ B ≤ N, -10^8 ≤ C ≤ 10^8), значення яких описано вище. Міста нумеруються числами від 1 до N; столиця має номер 1. Гарантується, що час перельоту по кожному з рейсів буде строго додатним.
Вивести N - 1 рядок. У i-му з них має міститись найменший час у хвилинах, за який можна долетіти зі столиці у місто з номером i + 1. Якщо до якогось міста дістатись неможливо, то виведіть у відповідному рядку число -1.