eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Олімпійські Авіалінії

Олімпійські Авіалінії

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Імператор Олімпії вирішив з’єднати N міст імперії повітряним транспортом. Придворному програмісту було наказано написати програму під назвою ОлімпБуд, яка спрощує процес побудови карти авіарейсів. Ця програма має виконувати операції двох типів, кожна з яких залежить від трьох параметрів A, B і C:

  1. Створити новий рейс з міста A до міста B, переліт по якому триває C хвилин.

  2. Розглянути всі авіарейси, які починаються в місті 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^8C 10^8), значення яких описано вище. Міста нумеруються числами від 1 до N; столиця має номер 1. Гарантується, що час перельоту по кожному з рейсів буде строго додатним.

Вихідні дані

Вивести N - 1 рядок. У i-му з них має міститись найменший час у хвилинах, за який можна долетіти зі столиці у місто з номером i + 1. Якщо до якогось міста дістатись неможливо, то виведіть у відповідному рядку число -1.

Приклад

Вхідні дані #1
4 3
1 1 2 10
2 1 3 -9
1 1 3 8
Вихідні дані #1
9
8
-1
Автор Ярослав Твердохліб
Джерело 2013 XXVI Всеукраїнська олімпіада з інформатики, Луганськ, Березень 17 - 21, тур 1