{"raw_statement":[{"iden":"background","content":"## 本题疑似是错题，详情见 [讨论](/discuss/1032942)。\n\n「{!@@(*@@￥';l]dw@)%)%&^_^}（可恶的人类！我一定会回来的！）」 \n\n它将飞船拉到了最高速度，试图离开这个充满人类的地狱。\n\n……"},{"iden":"statement","content":"过了那么多年，外星人的飞船速度早已比不过地球的飞船。因此，它决定使用折跃点逃离。\n\n平面地图上有 $n$ 个折跃点，坐标分别为 $(x_i,y_i)$。某些折跃点之间有双向空间隧道连接，共 $m$ 条隧道，每条隧道分别连接折跃点 $u_i,v_i$，且激活该隧道需要消耗 $w_i$ 单位能量。**请注意，为了保证空间隧道之间互不干扰，对于任意两条空间隧道 $\\bm{i,j}$，都保证连接点 $\\bm{u_i,v_i}$ 与点 $\\bm{u_j,v_j}$ 的线段没有交点。保证不存在起点和终点都相同的两条空间隧道。**\n\n外星人的科技非常神奇，因此为了成功折跃离开，外星人必须经过地图上的所有折跃点 **至少一次**，它可以从任意一点开始折跃并从任意一点结束折跃，最终，外星人所花费的总能量为激活路径上所有隧道所消耗能量的 **按位或运算和**。经过两次或两次以上同一隧道只需激活一次该隧道。\n\n外星人的飞船上拥有 $x$ 单位能量，因此，它所选择的折跃方案花费的总能量不能超过 $x$。为了拦截外星人，地方可以执行以下操作任意多次：\n\n+ 选择一条连接 $u$ 和 $v$ 的双向隧道（你需要保证在点 $u$ 和 $v$ 之间存在双向隧道连接）；\n+ 将激活它所需要的能量增加 $w$（$w\\ge0$ 且操作后激活该通道所需要的能量不能超过 $2^{31}-1$）。\n\n其中，$u,v,w$ 都可以自行指定。**每次操作所需要的代价为 $w$ 的二进制表示下 $1$ 的个数。**（即 `c++` 中的 `__builtin_popcount()` 函数）\n\n为了赎罪，你需要设计一种操作方案，使得外星人无法通过折跃逃离，并最小化该方案所需要的代价。"},{"iden":"input","content":"从标准输入读入数据。\n\n输入的第一行包含 $1$ 个正整数 $W$，表示该测试点的评分参数。\n\n输入的第二行包含 $3$ 个整数 $n,m,x$，分别表示折跃点个数，双向隧道条数以及外星人飞船上拥有的能量。\n\n第 $3$ 至 $(n+2)$ 行，第 $(i+2)$ 行有 $2$ 个整数 $x_i,y_i$，表示第 $i$ 个折跃点的坐标。\n\n接下来 $m$ 行，每行 $3$ 个整数 $u_i,v_i,w_i$，表示每条双向隧道连接的两个折跃点和激活所需能量。"},{"iden":"output","content":"输出到标准输出。\n\n**本题采用自定义校验器（special judge）评测。**\n\n输出的第一行应包含一个非负整数 $k$，表示操作总次数。\n\n接下来 $k$ 行，每行一次操作，形如 $u~v~w$，表示将激活连接 $u$ 和 $v$ 的双向隧道所需能量增加 $w$。\n\n你需要保证 $0\\le k\\le 10000$，否则将被判定为不合法答案。"},{"iden":"note","content":"**【样例解释】**\n+ **样例 1 解释：**  \n经过操作后的平面地图如下图所示（省略坐标轴）：  \n![](https://cdn.luogu.com.cn/upload/image_hosting/cbg7sir6.png)  \n由于与 $2$ 号折跃点相连的空间隧道所需要的激活能量全部为 $10$，所以成功折跃所需要的能量至少为 $10$，因此外星人无法通过折跃逃离，代价为 $1$，显然不存在代价更小的操作方案。\n\n***\n\n**【评分方式】**\n\n对于每个测试点，如果你的操作方案不合法或使得外星人能够成功通过折跃逃离，你将在该测试点得到  $0$ 分。\n\n否则，设该测试点的评分参数为 $W$，标准答案的代价为 $a$，你的操作方案的代价为 $b$，则你的分数 $s$ 将由下列公式给出：\n\n$$\ns=\\max\\left(1-\\frac{b-a}{a}\\times W,0\\right)\\times10\n$$\n\n***\n\n**【数据范围】** \n\n对于 $100\\%$ 的数据，$12\\le n\\le 53280$，$n-1\\le m\\le 3n-6$，$0\\le x<2^{31}-1$，$0\\le|x_i|,|y_i|\\le3\\times10^4$，$0\\le w_i<2^{31}$，$1\\le W\\le 1000$。\n\n|测试点编号|$n=$|$m=$|$W=$|数据随机生成|\n|:--:|:--:|:--:|:--:|:--:|\n|$1$|$12$|$26$|$1000$|否|\n|$2$|$12$|$26$|$1$|是|\n|$3$|$200$|$579$|$2$|是|\n|$4$|$500$|$1482$|$5$|是|\n|$5$|$5000$|$14971$|$5$|否|\n|$6$|$5000$|$14962$|$1$|是|\n|$7$|$10656$|$30188$|$1000$|否|\n|$8$|$10656$|$30188$|$5$|否|\n|$9$|$53280$|$150960$|$1000$|否|\n|$10$|$53280$|$150960$|$1000$|否|\n\n***\n\n**【校验器】**\n\n为了方便测试，在 $\\texttt{intercept}$ 目录下我们下发了 $\\texttt{checker.cpp}$ 文件。你可以编译该文件，并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致，你不需要也不应该关心其代码的具体内容。\n\n编译命令为：\n\n```plain\ng++ checker.cpp -o checker -std=c++14\n```\n\n使用方式为：\n\n```\n./checker <inputfile> <outputfile> <answerfile>\n```\n\n校验器可能会返回以下状态中的其中一种：\n\n+ $\\texttt{accepted}$：表示你的输出完全正确。\n+ $\\texttt{points } x$：表示你的输出部分正确，可以在该测试点得到比例为 $x$ 的分数。\n+ $\\texttt{wrong answer}$：表示你在该测试点得到 $0$ 分。\n\n\n对于所有非 $\\texttt{accepted}$ 状态，校验器接下来会输出以下信息中的一种：\n\n+ $\\texttt{A}$：表示你的输出不合法。\n+ $\\texttt{B x y}$：表示你的输出方案的代价为 $x$，标准答案为 $y$。\n+ $\\texttt{C}$：表示你的输出方案使得外星人能够成功通过折跃逃离。\n\n***\n\n**【后记】**\n\n他知道，他将永远离开家乡了。他仍记得，在倒转时空前，指挥官最后的那句叮嘱。他花了几乎半辈子，终于建立了新的基地，重整了军队。他的目的，就是为了防止这一切重蹈覆辙。现在，基地被毁了，他被困在这暗淡无光的星系里。他终于醒悟了，一切都是早已被决定好的。  \n「指挥官，对不起。」  \n「舱室将在十秒后自毁。十。九。八。七……」  \n举起手枪，对准自己太阳穴。  \n「六。五。四。三……」  \n随着砰的一声，他无力地倒下了，眼里黯淡无光。  \n「二。一。」  \n巨响过后，无人将被铭记。"}],"translated_statement":null,"sample_group":[["1\n5 6 9\n0 1\n0 0\n0 -1\n-1 0\n1 0\n1 2 10\n1 4 1\n2 3 8\n3 4 5\n3 5 1\n1 5 1","1\n2 3 2"],["见附件中的 intercept2.in","见附件中的 intercept2.ans"],["见附件中的 intercept3.in","见附件中的 intercept3.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}