{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eRick 和他的同事们制作了一种新的放射性配方,许多坏家伙都在追捕他们。所以 Rick 想在坏家伙抓到他们之前,把他的遗产留给 Morty。\u003c/p\u003e\n\n\u003cp\u003e他们的宇宙中有 $$$n$$$ 个星球,编号从 $$$1$$$ 到 $$$n$$$。Rick 所在的星球编号为 $$$s$$$ (地球),他不知道 Morty 在哪里。众所周知,Rick 拥有一把传送枪。有了这把枪,他可以打开单向传送门,从他所在的星球到达任何其他星球 (包括该星球)。但是这把枪有限制,因为他还在使用免费试用版。\u003c/p\u003e\n\n\u003cp\u003e默认情况下,他不能用这把枪打开任何传送门。在销售这些枪支的网站上有 $$$q$$$ 个选购计划。每次你购买一个计划后,你只能使用它一次;但如果你想再次使用,可以再次购买。\u003c/p\u003e\n\n\u003cp\u003e网站上的选购计划有三种类型:\u003c/p\u003e\n\u003col\u003e\n\u003cli\u003e 有了该类型的计划,你可以从星球 $$$v$$$ 打开传送门到达星球 $$$u$$$。 \u003c/li\u003e\n\u003cli\u003e 有了该类型的计划,你可以从星球 $$$v$$$ 打开传送门到达下标范围在 $$$[l,r]$$$ 内的任何星球。 \u003c/li\u003e\n\u003cli\u003e 有了该类型的计划,你可以从下标范围在 $$$[l,r]$$$ 内的任何星球打开传送门到达星球 $$$v$$$。 \u003c/li\u003e\n\u003c/ol\u003e\n\n\u003cp\u003eRick 不知道 Morty 在哪里,但 Unity 将会通知他,他希望准备好找到 Morty 并立即开始旅程。所以对于每个星球 (包括地球本身),他想知道从地球到该星球所需的最少资金。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含三个整数 $$$n,q,s$$$ $$$(1 \\leq n,q \\leq 10^5, ~1 \\leq s \\leq n)$$$,分别表示星球数量、选购计划的数量、地球的下标。\u003c/p\u003e\n\n\u003cp\u003e接下来的 $$$q$$$ 行包含了各个选购计划。每行以一个数 $$$t$$$ $$$(1 \\leq t \\leq 3)$$$ 开头,表示该选购计划的类型。若 $$$t\u003d1$$$,则后面跟着三个整数 $$$v,u,w$$$ $$$(1 \\leq v,u \\leq n,~1 \\leq w \\leq 10^9)$$$,其中 $$$w$$$ 是该计划的成本。否则,后跟四个整数 $$$v,l,r,w$$$,其中 $$$w$$$ 是该计划的成本。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一行,打印 $$$n$$$ 个整数。第 $$$i$$$ 个整数表示从地球到达第 $$$i$$$ 个星球所需的最少资金;如果无法抵达那个星球,则以 $$$-1$$$ 表示。\u003c/p\u003e"}},{"title":"示例1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 5 1\n2 3 2 3 17\n2 3 2 2 16\n2 2 2 3 3\n3 3 1 1 12\n1 3 3 17\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 28 12 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 1\n3 4 1 3 12\n2 2 3 4 10\n1 2 4 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 -1 -1 12 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个样例测试中,Rick 可以购买第 $$$4$$$ 个计划一次,然后购买第 $$$2$$$ 个计划,以便到达编号为 $$$2$$$ 的星球。\u003c/p\u003e"}}]}