{"trustable":false,"sections":[{"title":"Description","value":{"format":"MD","content":"给定一个 $n$ 个点,$m$ 条有向边的带非负权图,请你计算从 $s$ 出发,到每个点的距离。\n\n数据保证你能从 $s$ 出发到任意点。"}},{"title":"Input","value":{"format":"MD","content":"第一行为三个正整数 $n, m, s$。\n第二行起 $m$ 行,每行三个非负整数 $u_i, v_i, w_i$,表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。"}},{"title":"Output","value":{"format":"MD","content":"输出一行 $n$ 个空格分隔的非负整数,表示 $s$ 到每个点的距离。"}},{"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\n"}},{"title":"Hint","value":{"format":"MD","content":"样例解释请参考 \u003ca href\u003d\u0027https://www.luogu.org/problemnew/show/P3371\u0027 target\u003d\u0027_blank\u0027\u003e数据随机的模板题\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\n本题数据可能会持续更新,但不会重测,望周知。\n\n2018.09.04 数据更新 from @zzq"}},{"title":"Easter Egg","value":{"format":"MD","content":"2018 年 7 月 19 日,某位同学在 \u003ca href\u003d\u0027https://www.luogu.org/problemnew/show/P4768\u0027 target\u003d\u0027_blank\u0027\u003eNOI Day 1 T1 归程\u003c/a\u003e 一题里非常熟练地使用了一个广为人知的算法求最短路。\n\n然后呢?\n\n$100 \\rightarrow 60$;\n\n$\\text{Ag} \\rightarrow \\text{Cu}$;\n\n最终,他因此没能与理想的大学达成契约。\n\n小 F 衷心祝愿大家不再重蹈覆辙。"}}]}