Dendromark 的王子，高贵的 Stegan，因其挚爱父亲的离世而陷入悲伤。在通过辛普森法则计算各种梯形面积来探寻父亲命运的徒劳挣扎后，当一切希望破灭时，一位精灵向他伸出了援手。精灵给了他一棵树，让他去驾驭并照料。后来精灵告诉他：“看！仔细看！你看到了吗？这棵树很特别，因为它有偶数个顶点。如果你能找到一种最佳的配对方式，使得这些顶点的配对总代价尽可能小，你就能发现你父亲离世的真相。但首先，你得弄清楚配对的代价是什么；它的秘密在于生命的意义。”
身为一名伟大的数学家，Stegan 知道生命的真正意义在于这句话：“To be xor not to be”（以及随后的几行，但这与我们无关）。因此他推断出，对于一对顶点，它们配对的代价是连接这两个顶点的简单路径上所有边权值的按位异或和。
不幸的是，上天并没有赋予 Stegan 计算机科学方面的天赋，所以他不知道如何解决这个问题，于是他来向你求助。
形式化地说，给定一棵有 $N$ 个顶点的树，其中 $N$ 为偶数。每条边都有一个权值。对于一对顶点 $(u, v)$，我们定义它们配对的代价为连接这两个顶点的简单路径上所有边权值的按位异或和。
你需要找到一种将顶点划分为 $\frac{N}{2}$ 对的方法，使得它们的总代价之和尽可能小。由于要求你找到真正的最小解可能过于困难，我们只要求你尽力而为，并将根据你的结果获得相应的分数。
输入格式
输入的第一行包含一个偶数 $N$，表示树的顶点数。接下来的 $N-1$ 行，每行包含 3 个空格分隔的数字 $u_i, v_i, w_i$，表示存在一条权值为 $w_i$ 的边连接 $u_i$ 和 $v_i$。$u_i$ 和 $v_i$ 均在 $1$ 到 $N$ 之间。
输出格式
第一行，输出你所选定的顶点配对的总代价。接下来的 $\frac{N}{2}$ 行，每行输出一对配对的节点索引。所有配对节点不得重复。
评分标准
对于每个测试组：
- 如果你的程序对某个测试用例没有生成有效的响应（超出时间限制、运行时错误），则该组得 0 分。
- 如果你输出的 $\frac{N}{2}$ 对节点不是对 $N$ 个节点的划分，或者与你输出的总代价不符，则该响应也被视为无效。
- 如果上述情况均未发生，你将根据以下公式获得分数：
$\displaystyle \text{group\_score} \cdot \text{min}\left\{ \left( \frac{ok\_cost_i}{out\_cost_i} \right) ^4\right\}$，其中：
- $i$ 遍历测试组中的所有测试用例
- $out\_cost_i$ 是你的解法为测试用例 $i$ 计算出的代价
- $ok\_cost_i$ 是测试用例 $i$ 的最优解
约束与说明
- $2 \leq N \leq 200$
- $N$ 为偶数
- $0 \leq w_i \leq 2^{24}$
- 按位异或（^）运算符返回一个数字，其二进制表示中，若两个操作数的对应位不同则为 1，相同则为 0。
| # | 分数 | 数据范围 |
|---|---|---|
| 1 | 3 | $N \leq 10, w_i \leq 64$ |
| 2 | 6 | $N \leq 14$ |
| 3 | 19 | $N \leq 40, w_i \leq 64$ |
| 4 | 8 | $N \leq 120, w_i \leq 16$ |
| 5 | 41 | $N \leq 120$ |
| 6 | 23 | 无额外限制 |
样例
输入格式 1
6 5 2 42 5 4 52 6 3 26 4 6 39 1 6 15
输出格式 1
54 1 6 3 5 4 2
说明
输入格式 2
4 1 2 4 3 4 5 2 3 1
输出格式 2
1 2 3 1 4
说明
