CF786B.Legacy

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.

There are n planets in their universe numbered from 1 to n. Rick is in planet number s (the earth) and he doesn't know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he's still using its free trial.

By default he can not open any portal by this gun. There are q plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.

Plans on the website have three types:

1. With a plan of this type you can open a portal from planet v to planet u.
2. With a plan of this type you can open a portal from planet v to any planet with index in range [l, r].
3. With a plan of this type you can open a portal from any planet with index in range [l, r] to planet v.

Rick doesn't known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

瑞克和他的同事们研发出了一种新型放射性配方，许多坏蛋正追捕他们。因此，瑞克希望在被坏蛋抓住之前，将自己的遗产交给莫蒂。

他们的宇宙中有 $n$ 颗行星，编号从 $1$ 到 $n$。瑞克目前位于编号为 $s$ 的行星（即地球），但他不知道莫蒂在哪儿。众所周知，瑞克拥有一把传送门枪。借助这把枪，他可以从当前所在的行星向任意其他行星（包括自身）单向打开一扇传送门。但由于他仍在使用该枪的免费试用版，因此该枪存在使用限制。

默认情况下，他无法用此枪打开任何传送门。售卖该枪的网站上共有 $q$ 种购买方案。每次购买一种方案后，你仅能使用它一次；但若需多次使用，可重复购买同一方案。

网站上的方案共分三类：

1. 购买此类方案后，你可以从行星 $v$ 向行星 $u$ 打开一扇传送门；
2. 购买此类方案后，你可以从行星 $v$ 向任意编号在区间 $[l,\,r]$ 内的行星打开一扇传送门；
3. 购买此类方案后，你可以从任意编号在区间 $[l,\,r]$ 内的行星向行星 $v$ 打开一扇传送门。

瑞克并不知道莫蒂所在的位置，但“合一”（Unity）将会告知他。他希望提前做好准备，以便在获知莫蒂位置后能立即启程。因此，对于每一颗行星（包括地球本身），他都想知道从地球出发到达该行星所需的最少花费。

The first line of input contains three integers n, q and s (1 ≤ n, q ≤ 105, 1 ≤ s ≤ n) — number of planets, number of plans and index of earth respectively.

The next q lines contain the plans. Each line starts with a number t, type of that plan (1 ≤ t ≤ 3). If t = 1 then it is followed by three integers v, u and w where w is the cost of that plan (1 ≤ v, u ≤ n, 1 ≤ w ≤ 109). Otherwise it is followed by four integers v, l, r and w where w is the cost of that plan (1 ≤ v ≤ n, 1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ 109).

输入的第一行包含三个整数 $n$、$q$ 和 $s$（$1 ≤ n, q ≤ 10^5$，$1 ≤ s ≤ n$），分别表示行星数量、计划数量以及地球的编号。

接下来的 $q$ 行描述了这些计划。每行以一个整数 $t$ 开头，表示该计划的类型（$1 ≤ t ≤ 3$）。若 $t = 1$，则其后跟随三个整数 $v$、$u$ 和 $w$，其中 $w$ 是该计划的代价（$1 ≤ v, u ≤ n$，$1 ≤ w ≤ 10^9$）；否则其后跟随四个整数 $v$、$l$、$r$ 和 $w$，其中 $w$ 是该计划的代价（$1 ≤ v ≤ n$，$1 ≤ l ≤ r ≤ n$，$1 ≤ w ≤ 10^9$）。

In the first and only line of output print n integers separated by spaces. i-th of them should be minimum money to get from earth to i-th planet, or  - 1 if it's impossible to get to that planet.

在输出的第一行且唯一一行中，打印 $n$ 个由空格分隔的整数。其中第 $i$ 个整数应为从地球到达第 $i$ 颗行星所需的最少金钱数；若无法到达第 $i$ 颗行星，则输出 $-1$。

In the first sample testcase, Rick can purchase 4th plan once and then 2nd plan in order to get to get to planet number 2.

在第一个样例测试用例中，Rick 可以先购买第 4 套方案一次，再购买第 2 套方案，从而到达编号为 2 的星球。