{"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\u003e瑞克和他的同事们制作了一种新的放射性配方,很多坏人都在追杀他们。所以瑞克想在坏人抓到他们之前把他的遗产交给莫蒂。\u003c/p\u003e\n\u003cp\u003e他们的宇宙中有n个星球,编号从1到n。里克在s号星球(地球),他不知道莫蒂在哪里。我们都知道,瑞克拥有一把传送门枪。有了这把枪,他可以打开从他所在的星球到任何其他星球(包括该星球)的单向传送门。但这把枪是有限制的,因为他还在使用它的免费试用。\u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/3b0b9090a8511052603466e16730af78?v\u003d1636954641\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \n\u003c/center\u003e\n\u003cp\u003e默认情况下,他不能通过这把枪打开任何门户。在销售这些枪的网站上有q计划。每次你购买一个计划,你只能使用一次,但如果你想更多地使用它,你可以再次购买它。\u003c/p\u003e\n\u003cp\u003e网站上有3种形式的计划:\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\u003cp\u003e瑞克不知道莫蒂在哪里,但团结会通知他,他想为他找到时做好准备,立即开始他的旅程。因此,对于每个星球(包括地球本身),他想知道他从地球到该星球所需的最低金额。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行输入包含三个整数n、q和s (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003eq\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003es\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) - 分别是行星的数量、计划的数量和地球的指数。\u003c/p\u003e\n\u003cp\u003e接下来的q行包含计划。每一行都以一个数字t开始,即该计划的类型(1≤t≤3)。如果t\u003d1,那么后面是三个整数v、u和w,其中w是该计划的成本。(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e, \u003ci\u003eu\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). 否则,它后面有四个整数v、l、r和w,其中w是该计划的成本。(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003el\u003c/i\u003e ≤ \u003ci\u003er\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e在输出的第一行,也是唯一的一行,打印由空格分隔的n个整数。其中第i个整数应该是从地球到第i个星球的最低资金,如果不可能到达该星球,则为-1。\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3 5 1\u003cbr\u003e2 3 2 3 17\u003cbr\u003e2 3 2 2 16\u003cbr\u003e2 2 2 3 3\u003cbr\u003e3 3 1 1 12\u003cbr\u003e1 3 3 17\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e0 28 12 \u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 3 1\u003cbr\u003e3 4 1 3 12\u003cbr\u003e2 2 3 4 10\u003cbr\u003e1 2 4 16\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e0 -1 -1 12 \u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试案例中,瑞克可以购买一次第4个计划,然后购买第2个计划,以便到达2号行星。\u003c/p\u003e"}}]}