{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"On July 19, 2018, a student demonstrated exceptional proficiency in using a well-known algorithm to find the shortest path in the problem \u003ca href\u003d\u0027https://www.luogu.org/problemnew/show/P4768\u0027 target\u003d\u0027_blank\u0027\u003eNOI Day 1 T1 归程\u003c/a\u003e.\n\nAnd then?\n\n$100 \\rightarrow 60$;\n\n$\\text{Ag} \\rightarrow \\text{Cu}$;\n\nAs a result, he failed to fulfill his dream of entering the ideal university.\n\nLittle F sincerely hopes that everyone will not repeat the same mistake."}},{"title":"Description","value":{"format":"MD","content":"Given a graph with $n$ vertices and $m$ directed edges with non-negative weights, please calculate the distance from $s$ to each vertex.\n\nIt is guaranteed that you can reach any vertex from $s$."}},{"title":"Input","value":{"format":"MD","content":"The first line contains three positive integers $n, m, s$.\nStarting from the second line, there are $m$ lines, each containing three non-negative integers $u_i, v_i, w_i$, indicating that there is a directed edge from $u_i$ to $v_i$ with a weight of $w_i$."}},{"title":"Output","value":{"format":"MD","content":"Output a line of $n$ non-negative integers separated by spaces, representing the distance from $s$ to each vertex."}},{"title":"Sample 1","value":{"format":"MD","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 6 1\n1 2 2\n2 3 2\n2 4 1\n1 3 5\n3 4 3\n1 4 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 2 4 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"For an explanation of the sample, please refer to the \u003ca href\u003d\u0027https://www.luogu.org/problemnew/show/P3371\u0027 target\u003d\u0027_blank\u0027\u003erandom data template problem\u003c/a\u003e.\n\n$1 \\leq n \\leq 10^5$;\n\n$1 \\leq m \\leq 2\\times 10^5$;\n\n$s \u003d 1$;\n\n$1 \\leq u_i, v_i\\leq n$;\n\n$0 \\leq w_i \\leq 10 ^ 9$,\n\n$0 \\leq \\sum w_i \\leq 10 ^ 9$.\n\nThe data for this problem may be updated, but there will be no rejudging. Please be aware.\n\nData updated on September 4, 2018, from @zzq"}}]}