P8596 “KDOI-02” An Intercepted Blockade

## 本题疑似是错题，详情见 [讨论](/discuss/1032942)。 「{!@@(*@@￥';l]dw@)%)%&^_^}（可恶的人类！我一定会回来的！）」 它将飞船拉到了最高速度，试图离开这个充满人类的地狱。 ……

This problem is suspected to be incorrect. For details, see the [discussion](/discuss/1032942)。 「{!@@(*@@￥';l]dw@)%)%&^_^} (Damn humans! I will come back!)」 It pushed the spaceship to its top speed, trying to leave this human-filled hell. …… After so many years, the alien spaceship was already slower than Earth’s spaceships. Therefore, it decided to escape using warp points. On a planar map, there are $n$ warp points with coordinates $(x_i,y_i)$. Some warp points are connected by bidirectional space tunnels, with a total of $m$ tunnels. Each tunnel connects warp points $u_i,v_i$, and activating this tunnel consumes $w_i$ units of energy. **Note that, to ensure that space tunnels do not interfere with each other, for any two space tunnels $\bm{i,j}$, the segments connecting $\bm{u_i,v_i}$ and $\bm{u_j,v_j}$ are guaranteed to have no intersection. It is guaranteed that there do not exist two space tunnels with the same start and end points.** The alien technology is very magical. To successfully warp away, the alien must pass through all warp points on the map **at least once**. It may start from any point and end at any point. In the end, the total energy it spends is the **bitwise OR sum** of the energy costs of activating all tunnels on its path. If it passes through the same tunnel two or more times, it only needs to activate that tunnel once. The alien spaceship has $x$ units of energy, so the total energy cost of its chosen warp plan cannot exceed $x$. To intercept the alien, our side may perform the following operation any number of times: + Choose a bidirectional tunnel connecting $u$ and $v$ (you must ensure there exists a bidirectional tunnel between points $u$ and $v$)； + Increase the energy required to activate it by $w$ ($w\ge0$, and after the operation, the energy required to activate this tunnel must not exceed $2^{31}-1$)。 Here, $u,v,w$ can be chosen freely. **The cost of each operation is the number of $1$ bits in the binary representation of $w$.** (i.e., the `__builtin_popcount()` function in `c++`) To atone, you need to design an operation plan that makes the alien unable to escape by warping, and minimize the total cost of this plan.

Read input from standard input. The first line contains $1$ positive integer $W$, representing the scoring parameter of this test point. The second line contains $3$ integers $n,m,x$, representing the number of warp points, the number of bidirectional tunnels, and the energy on the alien spaceship. Lines $3$ to $(n+2)$: line $(i+2)$ contains $2$ integers $x_i,y_i$, representing the coordinates of the $i$-th warp point. The next $m$ lines each contain $3$ integers $u_i,v_i,w_i$, representing the two warp points connected by each bidirectional tunnel and the energy required to activate it.

Output to standard output. **This problem uses a custom checker (special judge).** The first line should contain a non-negative integer $k$, representing the total number of operations. The next $k$ lines each describe one operation in the form $u~v~w$, meaning increasing the energy required to activate the bidirectional tunnel connecting $u$ and $v$ by $w$. You must ensure $0\le k\le 10000$, otherwise it will be judged as an invalid answer.

**[Sample Explanation]** + **Sample 1 Explanation:** The planar map after the operations is shown in the figure below (axes omitted):  Since all space tunnels connected to warp point $2$ require activation energy $10$, the energy required for a successful warp is at least $10$. Therefore, the alien cannot escape by warping. The cost is $1$, and obviously there is no operation plan with a smaller cost. *** **[Scoring Method]** For each test point, if your operation plan is invalid or still allows the alien to successfully escape by warping, you will get $0$ points for this test point. Otherwise, let the scoring parameter of this test point be $W$, the cost of the standard answer be $a$, and the cost of your operation plan be $b$. Then your score $s$ is given by: $$ s=\max\left(1-\frac{b-a}{a}\times W,0\right)\times10 $$ *** **[Constraints]** For $100\%$ of the data, $12\le n\le 53280$, $n-1\le m\le 3n-6$, $0\le x