题目背景

「{!@@(*@@￥';l]dw@)%)%&^_^}（可恶的人类！我一定会回来的！）」

它将飞船拉到了最高速度，试图离开这个充满人类的地狱。

……

题目描述

过了那么多年，外星人的飞船速度早已比不过地球的飞船。因此，它决定使用折跃点逃离。

平面地图上有 $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}$ 的线段没有交点。保证不存在起点和终点都相同的两条空间隧道。

外星人的科技非常神奇，因此为了成功折跃离开，外星人必须经过地图上的所有折跃点 至少一次，它可以从任意一点开始折跃并从任意一点结束折跃，最终，外星人所花费的总能量为激活路径上所有隧道所消耗能量的 按位或运算和。经过两次或两次以上同一隧道只需激活一次该隧道。

外星人的飞船上拥有 $x$ 单位能量，因此，它所选择的折跃方案花费的总能量不能超过 $x$。为了拦截外星人，地方可以执行以下操作任意多次：

• 选择一条连接 $u$ 和 $v$ 的双向隧道（你需要保证在点 $u$ 和 $v$ 之间存在双向隧道连接）；
• 将激活它所需要的能量增加 $w$（$w\ge0$ 且操作后激活该通道所需要的能量不能超过 $2^{31}-1$）。

其中，$u,v,w$ 都可以自行指定。每次操作所需要的代价为 $w$ 的二进制表示下 $1$ 的个数。（即 c++ 中的 __builtin_popcount() 函数）

为了赎罪，你需要设计一种操作方案，使得外星人无法通过折跃逃离，并最小化该方案所需要的代价。

输入格式

从标准输入读入数据。

输入的第一行包含 $1$ 个正整数 $W$，表示该测试点的评分参数。

输入的第二行包含 $3$ 个整数 $n,m,x$，分别表示折跃点个数，双向隧道条数以及外星人飞船上拥有的能量。

第 $3$ 至 $(n+2)$ 行，第 $(i+2)$ 行有 $2$ 个整数 $x_i,y_i$，表示第 $i$ 个折跃点的坐标。

接下来 $m$ 行，每行 $3$ 个整数 $u_i,v_i,w_i$，表示每条双向隧道连接的两个折跃点和激活所需能量。

输出格式

输出到标准输出。

本题采用自定义校验器（special judge）评测。

输出的第一行应包含一个非负整数 $k$，表示操作总次数。

接下来 $k$ 行，每行一次操作，形如 $u~v~w$，表示将激活连接 $u$ 和 $v$ 的双向隧道所需能量增加 $w$。

你需要保证 $0\le k\le 10000$，否则将被判定为不合法答案。

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

提示

【样例解释】

• 样例 1 解释：
  经过操作后的平面地图如下图所示（省略坐标轴）：
  
  由于与 $2$ 号折跃点相连的空间隧道所需要的激活能量全部为 $10$，所以成功折跃所需要的能量至少为 $10$，因此外星人无法通过折跃逃离，代价为 $1$，显然不存在代价更小的操作方案。

---

【评分方式】

对于每个测试点，如果你的操作方案不合法或使得外星人能够成功通过折跃逃离，你将在该测试点得到 $0$ 分。

否则，设该测试点的评分参数为 $W$，标准答案的代价为 $a$，你的操作方案的代价为 $b$，则你的分数 $s$ 将由下列公式给出：

$$s=\max\left(1-\frac{b-a}{a}\times W,0\right)\times10 $$

---

【数据范围】

对于 $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=$	$m=$	$W=$	数据随机生成
$1$	$12$	$26$	$1000$	否
$2$			$1$	是
$3$	$200$	$579$	$2$
$4$	$500$	$1482$	$5$
$5$	$5000$	$14971$		否
$6$		$14962$	$1$	是
$7$	$10656$	$30188$	$1000$	否
$8$			$5$
$9$	$53280$	$150960$	$1000$
$10$

---

【校验器】

为了方便测试，在 $\texttt{intercept}$ 目录下我们下发了 $\texttt{checker.cpp}$ 文件。你可以编译该文件，并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致，你不需要也不应该关心其代码的具体内容。

编译命令为：

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

使用方式为：

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

校验器可能会返回以下状态中的其中一种：

• $\texttt{accepted}$：表示你的输出完全正确。
• $\texttt{points } x$：表示你的输出部分正确，可以在该测试点得到比例为 $x$ 的分数。
• $\texttt{wrong answer}$：表示你在该测试点得到 $0$ 分。

对于所有非 $\texttt{accepted}$ 状态，校验器接下来会输出以下信息中的一种：

• $\texttt{A}$：表示你的输出不合法。
• $\texttt{B x y}$：表示你的输出方案的代价为 $x$，标准答案为 $y$。
• $\texttt{C}$：表示你的输出方案使得外星人能够成功通过折跃逃离。

---

【后记】

他知道，他将永远离开家乡了。他仍记得，在倒转时空前，指挥官最后的那句叮嘱。他花了几乎半辈子，终于建立了新的基地，重整了军队。他的目的，就是为了防止这一切重蹈覆辙。现在，基地被毁了，他被困在这暗淡无光的星系里。他终于醒悟了，一切都是早已被决定好的。
「指挥官，对不起。」
「舱室将在十秒后自毁。十。九。八。七……」
举起手枪，对准自己太阳穴。
「六。五。四。三……」
随着砰的一声，他无力地倒下了，眼里黯淡无光。
「二。一。」
巨响过后，无人将被铭记。