{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e经过一天的努力,ALPC终于完成了他们的终极情报系统,当然这是为了ACM比赛……\u003cbr\u003e现在,情报部门的负责人kzc_tc(曾经的代号是48,但现在是0),突然从一名情报人员那里获得了关于ALPC战略方向和未来发展的重要信息。因此,他需要紧急通知所有情报人员,于是决定使用情报系统(kzc_tc通知一个人,然后这个人通知其他人,依此类推,直到所有人都知道)。\u003cbr\u003e我们知道这是一项危险的工作。每次信息传递只能通过固定的途径,从一个固定的人到另一个固定的人,不能互换,但两个人之间可能有多种传递方式。每次传递的成本为Ci(1 \u0026lt;\u003d Ci \u0026lt;\u003d 100000),如果通知ALPC情报机构的某些人,他们的总成本就是这些成本的总和。\u003cbr\u003e好消息是,如果两个人可以直接或间接地通过其他人相互通知,那么他们属于同一分支(kzc_tc也属于一个分支!)。在这种情况下,他们之间的成本将被忽略。情报机构中的分支数量不超过一百。\u003cbr\u003e由于ALPC资金目前紧张,kzc_tc现在已经拥有了他情报系统中所有人的关系,他想编写一个程序,以确保以最小成本确保每个人都知道这些情报。\u003cbr\u003e真是让人烦恼啊!\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"有几个测试用例。\u003cbr\u003e在每种情况下,第一行是一个整数N(0\u0026lt; N \u0026lt;\u003d 50000),表示情报人员的数量,包括kzc_tc。他们的代号从0到N-1编号。然后是M(0\u0026lt;\u003d M \u0026lt;\u003d 100000),表示传递方式的数量。\u003cbr\u003e接下来的M行,每行包含三个整数X、Y和C,表示X号人员向Y号人员传递信息的成本为C。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"通知所有人所需的最小总成本。\u003cbr\u003e相信kzc_tc的能力!他总能找到一种方法与所有其他情报人员进行沟通。\u003cbr\u003e"}},{"title":"样例","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 3\r\n0 1 100\r\n1 2 50\r\n0 2 100\r\n3 3\r\n0 1 100\r\n1 2 50\r\n2 1 100\r\n2 2\r\n0 1 50\r\n0 1 100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e150\r\n100\r\n50\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}