| Codeforces Round 406 (Div. 1) |
|---|
| Закончено |
Рик и его коллеги сделали новую радиактивную формулу, и она понадобилась многим плохим парням. Поэтому Рик хочет оставить свое наследство Морти до того, как плохие парни поймают его.
Всего есть n планет в их вселенной, пронумерованных от 1 до n. Рик находится на планете номер s (планетя Земля) и он не знает, где сейчас Морти. Всё, что мы знаем, что Рику принадлежит портальное оружие. С помощью этой пушки он может открыть односторонний портал с одной планеты на любую другую (включая эту планету). Но у этого оружия есть ограничения, потому что он все еще использует бесплатную версию.
По умолчанию он не может открыть любой портал этим оружием. Всего есть q планов на сайте, который продает это оружие. Каждый раз, когда происходит покупка плана, его можно использовать только один раз. Но можно покупать один и тот же план произвольное количество раз.
Планы на сайте имеют три типа:
- С планом этого типа вы можете открыть портал с планеты v до планеты u.
- С планом этого типа вы можете открыть портал с планеты v до любой планеты с номером из диапазона [l, r].
- С планом этого типа вы можете открыть портал с любой планеты с номером из диапазона [l, r] до планеты v.
Рик не знает, где находится Морти, но Юнити собирается проинформировать его, и он хочет быть готовым к тому, чтобы начать свое путешествие немедленно. Поэтому для каждой планеты (включая Землю) он хочет знать минимальное количество денег, которое ему необходимо чтобы добраться от Земли до этой планеты.
Первая строка входных данных содержит три целых числа n, q и s (1 ≤ n, q ≤ 105, 1 ≤ s ≤ n) — количество планет, количество планов и номер планеты Земля соответственно.
Следующие q строк содержат планы. Каждая строка начинается целым числом t — тип плана (1 ≤ t ≤ 3). Если t = 1, тогда далее следуют три числа v, u и w, где w — стоимость плана (1 ≤ v, u ≤ n, 1 ≤ w ≤ 109). Иначе следуют четыре числа v, l, r и w, где w — стоимость плана (1 ≤ v ≤ n, 1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ 109).
В первой и единственной строке выведите n целых чисел разделенных пробелами. i-е из них должно быть равно минимальному количеству денег, необходимых, чтобы добраться с планеты Земля до i-й планеты, или - 1, если невозможно добраться до этой планеты.
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
0 28 12
4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16
0 -1 -1 12
В первом тестовом примере, Рик покупает 4-й план единожды, далее 2-й план, чтобы добраться до планеты номер 2.
