题目描述
瑞克和他的同事发明了一种新的放射性婴儿食品中。很多坏人都在追杀他们。所以瑞克想在坏人抓到他们之前把他的遗产交给莫蒂。
宇宙中有m个行星，编号为从1到n。瑞克在编号为s（地球）的行星，他不知道莫蒂在哪里。众所周知，瑞克有一把传送枪。有了这把枪，他可以打开从他所在的星球到任何其他星球（包括自己所在的星球）的单向传送们，但这把枪的使用是要付费的。
在网上有Q个使用传送枪的方案出售，每购买一个计划可以使用一次传送枪。如果你想继续使用它，你可以再次购买。每个方案的购买次数都是无限的。
网络上一共有三种方案可供选择：
（1）开启一扇从星球v到星球u的传送门；
（2）开启一扇从星球v到编号在[l,r]范围内任何一个星球的传送门。（即通过这扇传送门可以从一个星球通往多个星球。）
（3）开启一扇从编号在[l,r]范围内任何一个星球到星球v的传送门。（即通过这扇传送门可以从多个星球出发到达同一个星球。）
瑞克不知道莫蒂在哪里，但尤妮蒂会通知他，他想为找到莫蒂做好准备，并立即开始他的旅程。所以对于每个行星（包括地球本身），他想知道他从地球到相应行星所需的最少花费。
输入
输入数据的第1行：包括三个用空格隔开的整数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 表示第三种方案，表示从编号在[l,r]范围内任何一个星球到星球v的传送门的花费为w。
输出
输出1行：n个用空格隔开的整数,分别表示从地球到第i个星球所需的最小钱数。如果不能到达那个星球，输出-1。
说明:在第一组测试样例里，Rick 可以先购买第 4个方案,再购买第 2个方案从而到达标号为2的星球。
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
提示
对于100% 的数据，1≤n,q≤105 ，1≤s≤n，1≤v,u≤n，1≤l≤r≤n，1≤w≤109。