Рик и его коллеги сделали новую радиактивную формулу, и она понадобилась многим плохим парням. Поэтому Рик хочет оставить свое наследство Морти до того, как плохие парни поймают его.
Всего есть n планет в их вселенной, пронумерованных от 1 до n. Рик находится на планете номер s (планетя Земля) и он не знает, где сейчас Морти. Всё, что мы знаем, что Рику принадлежит портальное оружие. С помощью этой пушки он может открыть односторонний портал с одной планеты на любую другую (включая эту планету). Но у этого оружия есть ограничения, потому что он все еще использует бесплатную версию.
По умолчанию он не может открыть любой портал этим оружием. Всего есть q планов на сайте, который продает это оружие. Каждый раз, когда происходит покупка плана, его можно использовать только один раз. Но можно покупать один и тот же план произвольное количество раз.
Планы на сайте имеют три типа:
- С планом этого типа вы можете открыть портал с планеты v до планеты u.
- С планом этого типа вы можете открыть портал с планеты v до любой планеты с номером из диапазона [l, r].
- С планом этого типа вы можете открыть портал с любой планеты с номером из диапазона [l, r] до планеты v.
Рик не знает, где находится Морти, но Юнити собирается проинформировать его, и он хочет быть готовым к тому, чтобы начать свое путешествие немедленно. Поэтому для каждой планеты (включая Землю) он хочет знать минимальное количество денег, которое ему необходимо чтобы добраться от Земли до этой планеты.
Выходные данные
В первой и единственной строке выведите n целых чисел разделенных пробелами. i-е из них должно быть равно минимальному количеству денег, необходимых, чтобы добраться с планеты Земля до i-й планеты, или - 1, если невозможно добраться до этой планеты.
Примечание
В первом тестовом примере, Рик покупает 4-й план единожды, далее 2-й план, чтобы добраться до планеты номер 2.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16
|
0 -1 -1 12
|