{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"安德鲁正在担任系统管理员,并计划在公司建立一个新的网络。公司里将有N个中心,它们可以通过电缆相互连接。由于公司的每个员工都必须能够访问整个网络,因此每个中心必须可以通过电缆从任何其他中心访问(可能需要一些中间中心)。\n\u003cbr\u003e由于有不同类型的电缆可用,而且较短的电缆更便宜,因此有必要制定这样一个中心连接计划,使得单根电缆的最大长度最小化。另一个问题是,由于兼容性问题和建筑几何限制,并非每个中心都可以连接到任何其他中心。当然,安德鲁会为您提供所有关于可能中心连接的必要信息。\n\u003cbr\u003e您需要帮助安德鲁找到连接中心的方法,以满足上述所有条件。"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含两个整数:N - 网络中心的数量(2 \u003c\u003d N \u003c\u003d 1000)和M - 可能的中心连接数量(1 \u003c\u003d M \u003c\u003d 15000)。所有中心的编号从1到N。接下来的M行包含关于可能连接的信息 - 可以连接的两个中心的编号以及连接它们所需的电缆长度。长度是不超过10\u003csup\u003e6\u003c/sup\u003e的正整数。不会有超过一种连接两个中心的方式。一个中心不能连接到自身。始终至少有一种连接所有中心的方式。"}},{"title":"输出","value":{"format":"HTML","content":"首先输出您的中心连接计划中单根电缆的最大长度(您应该最小化的值)。然后输出您的计划:首先输出P - 使用的电缆数量,然后输出P对整数 - 对应电缆连接的中心编号。用空格和/或换行符分隔数字。"}},{"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\u003e4 6\r\n1 2 1\r\n1 3 1\r\n1 4 2\r\n2 3 1\r\n3 4 1\r\n2 4 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n4\r\n1 2\r\n1 3\r\n2 3\r\n3 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}