{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlex是\u003ci\u003e国内网络公司\u003c/i\u003e的系统管理员。他的网络连接公寓,横跨多栋建筑物。\u003c/p\u003e\u003cp\u003e网络在扩张,Alex需要设计一个新的网络段。他有一张地图,显示了需要连接的公寓以及可能的连接。每条连接连接两个公寓,对于每个可能的连接,都知道其长度。目标是使所有公寓都连接起来(可能通过其他公寓)。\u003c/p\u003e\u003cp\u003e\u003ci\u003e国内网络公司\u003c/i\u003e在最近的电缆店购买电缆。不幸的是,该店只出售5类和6类电缆,价格分别为\u003ci\u003ep\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e和\u003ci\u003ep\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e卢布每米。此外,店里只有\u003ci\u003eq\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e米5类电缆和\u003ci\u003eq\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e米6类电缆可用。\u003c/p\u003e\u003cp\u003e帮助Alex解决一个困难问题:制定一个可能的最小成本的新网络建设计划。计划包括要建立的连接列表和每个连接的电缆类别(每个连接应该是5类或6类电缆的单块)。计划的成本是所有电缆成本的总和。计划中使用的每种类别电缆的总长度不应超过商店中可用的电缆数量。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入文件的第一行包含两个数字:\u003ci\u003en\u003c/i\u003e — 要连接的公寓数量和 \u003ci\u003em\u003c/i\u003e — 可能的连接数量 (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1000, 1 ≤ \u003ci\u003em\u003c/i\u003e ≤ \u003cnobr\u003e10 000\u003c/nobr\u003e)。\u003c/p\u003e\u003cp\u003e接下来的 \u003ci\u003em\u003c/i\u003e 行包含可能的连接描述。每个描述包括三个整数:\u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e 和 \u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — 可以通过该连接连接的公寓以及 \u003ci\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — 连接长度(0 ≤ \u003ci\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 100)。公寓从1到 \u003ci\u003en\u003c/i\u003e 编号。\u003c/p\u003e\u003cp\u003e输入文件的最后一行包含四个整数:\u003ci\u003ep\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e, \u003ci\u003eq\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e, \u003ci\u003ep\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e 和 \u003ci\u003eq\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e — 5类和6类电缆的价格和数量(1 ≤ \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eq\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ \u003cnobr\u003e10 000\u003c/nobr\u003e)。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e如果所有公寓都可以用现有电缆连接,输出 \u003ci\u003en\u003c/i\u003e 行 — 最佳网络建设计划。计划的第一行必须包含计划的成本。计划的其他行必须包含两个整数:\u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — 要创建的连接编号和 \u003ci\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — 要创建的电缆类别。连接按照它们在输入文件中指定的顺序从1到 \u003ci\u003em\u003c/i\u003e 编号。如果有多个最佳计划,则输出其中任意一个。\u003c/p\u003e\u003cp\u003e如果没有符合所有要求的计划,则输出单词 “\u003ctt\u003eImpossible\u003c/tt\u003e”。\u003c/p\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\u003e6 7\r\n1 2 7\r\n2 6 5\r\n1 4 8\r\n2 3 5\r\n3 4 5\r\n5 6 6\r\n3 5 3\r\n2 11 3 100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e65\r\n1 5\r\n2 6\r\n4 6\r\n5 6\r\n7 5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}