{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e农夫约翰想在他的农场建立一条电话线。不幸的是,电话公司不合作,所以他需要支付一些连接他的农场与电话系统所需的电缆费用。\u003c/p\u003e\u003cp\u003e农场约翰的土地上散落着一些孤零零的电话杆,方便地编号为1..\u003ci\u003eN\u003c/i\u003e,其中没有任何电缆连接它们。一共有\u003ci\u003eP\u003c/i\u003e (1 ≤ \u003ci\u003eP\u003c/i\u003e ≤ 10,000) 对杆子可以通过一根电缆连接起来;其余的距离太远。\u003c/p\u003e\u003cp\u003e第\u003ci\u003ei\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 (1 ≤ \u003ci\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 1,000,000) 单位。输入数据集中不会重复命名任何{\u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e}对。杆子1已经连接到电话系统,杆子\u003ci\u003eN\u003c/i\u003e在农场上。杆子1和\u003ci\u003eN\u003c/i\u003e需要通过一条电缆路径连接起来;其余的杆子可能被使用也可能不被使用。\u003c/p\u003e\u003cp\u003e事实证明,电话公司愿意为农夫约翾提供\u003ci\u003eK\u003c/i\u003e (0 ≤ \u003ci\u003eK\u003c/i\u003e \u0026lt; \u003ci\u003eN\u003c/i\u003e) 长度的免费电缆。超出这个数量,他将不得不支付一个等于他需要的最长剩余电缆长度的价格(每对杆子用一根单独的电缆连接),如果他不需要任何额外的电缆,则支付0。\u003c/p\u003e\u003cp\u003e确定农夫约翰必须支付的最小金额。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e* 第1行: 三个用空格分隔的整数: \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eP\u003c/i\u003e, 和 \u003ci\u003eK\u003c/i\u003e\u003cbr\u003e* 第2..\u003ci\u003eP\u003c/i\u003e+1行: 第\u003ci\u003ei\u003c/i\u003e+1行包含三个用空格分隔的整数: \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 \u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e* 第1行: 一个整数,农夫约翰可以支付的最小金额。如果无法将农场连接到电话公司,则打印-1。\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\u003e5 7 1\r\n1 2 5\r\n3 1 4\r\n2 4 8\r\n3 2 3\r\n5 2 9\r\n3 4 7\r\n4 5 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}