Задача #0177

На день рождения Шермат получил автобусные билеты. Сначала ему было грустно из-за этого, но он удивился, когда понял, что билеты не простые, а супер билеты. На данный момент у него есть \(m\) супер-билетов, и они делятся на три типа:
1. С этим билетом он может перейти от остановки \(a\) к остановке \(b\).
2. С этим билетом он может перейти от остановки \(a\) к любой остановке в диапазоне \([l, r]\).
3. С этим билетом он может перейти от любой остановки в диапазоне \([l, r]\) к остановке \(a\).

Для каждого билета указано время, необходимое для проезда.Всего \(n\) остановок, и Шермат стоит на остановке \(s\). Шермат хочет знать, наименьшее количество времени, необходимое для перехода от остановки \(s\) ко всем другим возможным остановкам. Расписание автобусов настолько плотное, что можно считать, что на пересадку автобуса на остановке не требуется времени.

Первая строка ввода содержит три целых числа \(n\), \(m\) и \(s\) - количество остановок, количество билетов и индекс остановки Шермата \((1 ≤ n, m ≤ 10^5, 1 ≤ s ≤ n)\). В следующих \(m\) строках даны билеты:

• \(1 \space a \space b \space t\) - это билет типа 1, по нему можно перейти от остановки \(a\) до остановки \(b\) за время \(t\).
• \(2 \space a \space l \space r \space t\) - это билет типа 2, с этим билетом можно перейти от остановки \(a\) к любой остановке в диапазоне \([l, r]\).
• \(3 \space a \space l \space r \space t\) - это билет типа 3, с этим билетом можно перейти с любой остановки в диапазоне \([l, r]\) до остановки \(a\).

Выведите \(n\) чисел, \(i\)-е из них должно быть равно минимальному времени, которое потребуется, чтобы пройти от остановки \(s\) до остановки \(i\), если невозможно перейти к остановке \(i\), выведите \(-1\).