CF786B Legacy

Rick 和他的同事们做出了一种新的放射性配方，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。 在宇宙中一共有 $n$ 个星球标号为 $1\sim n$。Rick 现在身处于标号为 $s$ 的星球（地球）但是他不知道 Morty 在哪里。 众所周知，Rick 有一个传送枪，他用这把枪可以制造出一个从他所在的星球通往其他星球（也包括自己所在的星球）的单行道路。但是由于他还在用免费版，因此这把枪的使用是有限制的。 默认情况下他不能用这把枪开启任何传送门。在网络上有 $q$ 个售卖这些传送枪的使用方案。每一次你想要实施这个方案时你都可以购买它，但是每次购买后只能使用一次。每个方案的购买次数都是无限的。 网络上一共有三种方案可供购买： * 开启一扇从星球 $v$ 到星球 $u$ 的传送门； * 开启一扇从星球 $v$ 到标号在 $[l,r]$ 区间范围内任何一个星球的传送门。（即这扇传送门可以从一个星球出发通往多个星球）； * 开启一扇从标号在 $[l,r]$ 区间范围内任何一个星球到星球 $v$ 的传送门。（即这扇传送门可以从多个星球出发到达同一个星球）； Rick 并不知道 Morty 在哪儿，但是 Unity 将要通知他 Morty 的具体位置，并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球（包括地球本身）他想要知道从地球到那个星球所需的最小钱数。

输入数据的第一行包括三个整数 $n,q,s$ 分别表示星球的数目，可供购买的方案数目以及地球的标号。 接下来的 $q$ 行表示 $q$ 种方案： * 输入 `1 v u w` 表示第一种方案，其中 $v,u$ 意思同上，$w$ 表示此方案价格； * 输入 `2 v l r w` 表示第二种方案，其中 $v,l,r$ 意思同上，$w$ 表示此方案价格； * 输入 `3 v l r w` 表示第三种方案，其中 $v,l,r$ 意思同上，$w$ 表示此方案价格。

输出一行用空格隔开的 $n$ 个整数分别表示从地球到第 $i$ 个星球所需的最小钱数。如果不能到达那个星球，输出 $-1$。

样例解释：在第一组测试样例里，Rick 可以先购买第 $4$ 个方案再购买第 $2$ 个方案从而到达标号为 $2$ 的星球。 对于 $100\%$ 的数据，有 $1\leq n,q\leq10^5,1\leq w\leq10^9,1\leq l,r\leq n$。