Problem Description

This problem is suspected to be incorrect. For details, see the discussion。

「{!@@(*@@￥';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.

Input Format

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 Format

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.

1
5 6 9
0 1
0 0
0 -1
-1 0
1 0
1 2 10
1 4 1
2 3 8
3 4 5
3 5 1
1 5 1

1
2 3 2

见附件中的 intercept2.in

见附件中的 intercept2.ans

见附件中的 intercept3.in

见附件中的 intercept3.ans

Hint

[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<2^{31}-1$, $0\le|x_i|,|y_i|\le3\times10^4$, $0\le w_i<2^{31}$, $1\le W\le 1000$。

Test Point ID	$n=$	$m=$	$W=$	Randomly Generated Data
$1$	$12$	$26$	$1000$	No
$2$			$1$	Yes
$3$	$200$	$579$	$2$
$4$	$500$	$1482$	$5$
$5$	$5000$	$14971$		No
$6$		$14962$	$1$	Yes
$7$	$10656$	$30188$	$1000$	No
$8$			$5$
$9$	$53280$	$150960$	$1000$
$10$

---

[Checker]

For convenience of testing, we provide the file $\texttt{checker.cpp}$ in the $\texttt{intercept}$ directory. You can compile it and use it to verify your output file. Note that it is not exactly the same as the checker used in the final judging, and you do not need and should not care about the specific code content.

The compilation command is:

g++ checker.cpp -o checker -std=c++14

Usage:

./checker <inputfile> <outputfile> <answerfile>

The checker may return one of the following statuses:

• $\texttt{accepted}$: your output is completely correct.
• $\texttt{points } x$: your output is partially correct, and you can get a score with ratio $x$ on this test point.
• $\texttt{wrong answer}$: you get $0$ points on this test point.

For all statuses other than $\texttt{accepted}$, the checker will then output one of the following messages:

• $\texttt{A}$: your output is invalid.
• $\texttt{B x y}$: the cost of your output plan is $x$, and the standard answer is $y$.
• $\texttt{C}$: your output plan allows the alien to successfully escape by warping.

---

[Epilogue]

He knew he would leave his homeland forever. He still remembered the commander’s last reminder before reversing spacetime. He spent almost half his life to finally build a new base and reorganize the army. His goal was to prevent all of this from happening again. Now, the base was destroyed, and he was trapped in this dimly lit galaxy. He finally realized that everything had already been decided.
“Commander, I’m sorry.”
“The cabin will self-destruct in ten seconds. Ten. Nine. Eight. Seven…”
He raised the pistol and aimed at his temple.
“Six. Five. Four. Three…”
With a bang, he collapsed weakly, his eyes dull and lifeless.
“Two. One.”
After the loud explosion, no one will be remembered.

Translated by ChatGPT 5