{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"你被指派设计连接广域网中某些点的网络。给定该区域中的一组点,以及可能连接点对的电缆的一组可能路线。对于两点之间的每条可能路线,你将得到连接这些点所需电缆的长度。请注意,两个给定点之间可能存在许多可能的路线。假定给定的可能路线连接(直接或间接地)该区域中的每两个点。\r\u003cbr\u003e你的任务是设计该区域的网络,以便每两个点之间都有连接(直接或间接的),并且所使用电缆的总长度是最小的(即所有点都相互连接,但不一定是通过直接电缆)。"}},{"title":"输入","value":{"format":"HTML","content":"输入文件包含多个数据集。每个数据集定义一个所需的网络。集合的第一行包含两个整数:第一个定义了给定点P的数量,第二个定义了给定点之间的路线R的数量。接下来的R行定义了点之间的给定路线,每行给出三个整数:前两个数字标识点,第三个给出路线的长度。这些数字用空格分隔。给定P\u003d0的数据集表示输入的结束。数据集之间用空行分隔。\r\u003cbr\u003e点的最大数量为50。给定路线的最大长度为100。可能路线的数量没有限制。节点用1到P(包括P)之间的整数进行标识。点i和j之间的路线可以表示为i j或j i。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个数据集,打印一个数字,表示整个设计网络所使用的电缆的总长度。"}},{"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\u003e1 0\r\n\r\n2 3\r\n1 2 37\r\n2 1 17\r\n1 2 68\r\n\r\n3 7\r\n1 2 19\r\n2 3 11\r\n3 1 7\r\n1 3 5\r\n2 3 89\r\n3 1 91\r\n1 2 32\r\n\r\n5 7\r\n1 2 5\r\n2 3 7\r\n2 4 8\r\n4 5 11\r\n3 5 10\r\n1 5 6\r\n4 2 12\r\n\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n17\r\n16\r\n26\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}