CF1218D.Xor Spanning Tree

In the galaxy far far away is the ancient interplanetary republic of Bubbleland, consisting of $N$ planets. Between them, there are $M$ bidirectional wormholes, each connecting a pair of planets. Bubbleland is a very centralized republic, having a capital planet Whiteplanet, from which any another planet can be reached using these wormholes. It is also guaranteed that no wormhole connects planet to itself and that no two different wormholes connect same pair of planets.

We call a path that begins at one planet, visits other planets and each of them at most once and returns to starting point a tour. Interplanetary Safety Regulations guarantee that each planet belongs to at most one tour and that there are at most $42$ tours.

After many eons of usage, wormholes need to be repaired and each wormhole has the cost $W_{i}$ which needs to be payed for reparation. Unfortunately, the Senate of Bubbleland is short on budget. Therefore, they have decided only to fix as many wormholes as they need in order to have all planets reachable from capital and to pay as little money as they have to for this repair. However the way in which the Senate calculates the cost is different. Cost of the set of reparations is binary xor of costs of each individual reparation, that is if reparations to be made have costs $A_{1},A_{2},...,A_{k}$, the cost of entire set is $A_{1} \oplus A_{2} \oplus ... \oplus A_{k}$.

Now the Senate would like to know how much money do they have to pay and also the number of different ways to achieve that cost modulo $1000000007$.

在遥远的银河系中，存在着古老的星际共和国——泡泡国（Bubbleland），它由 $N$ 颗行星组成。这些行星之间共有 $M$ 条双向虫洞，每条虫洞连接一对行星。泡泡国是一个高度中央集权的共和国，其首都为白星（Whiteplanet）；从该首都出发，可通过这些虫洞抵达其余任意一颗行星。同时保证：不存在连接某颗行星与其自身的虫洞，也不存在两条不同的虫洞连接完全相同的行星对。

我们称一条**环游路径（tour）**为：从某颗行星出发，途经若干其他行星（每颗行星至多访问一次），最终返回起点的路径。根据《星际安全条例》，每颗行星至多属于一个环游路径，且整个泡泡国中环游路径总数至多为 $42$ 条。

经过漫长岁月的使用，这些虫洞亟需维修；每条虫洞 $i$ 的维修费用为 $W_{i}$。不幸的是，泡泡国参议院预算紧张，因此决定：仅维修必要数量的虫洞，以确保所有行星仍能从首都白星抵达；并且在满足连通性前提下，使总维修费用尽可能低。但参议院计算总费用的方式较为特殊：总费用定义为所选各条虫洞维修费用的**按位异或（binary xor）**值。即，若选定维修的虫洞费用为 $A_{1},A_{2},...,A_{k}$，则整套维修方案的总费用为 $A_{1} \oplus A_{2} \oplus ... \oplus A_{k}$。

现在，参议院希望知道：
（1）所需支付的最少总费用；
（2）达成该最少总费用的不同维修方案数目（对 $1000000007$ 取模）。

First line of input contains two numbers $N (1 \leq N \leq 100.000)$, the number of planets and $M (1 \leq M \leq 100.041)$, the number of wormholes. Following $M$ lines contain three numbers $U, V (1 \leq U \neq V \leq N)$ and $W (1 \leq W \leq 100.000)$, meaning that there exists a wormhole connecting planets $U$ and $V$, with repair cost of $W$.

输入的第一行包含两个数字 $N (1 \leq N \leq 100.000)$（行星数量）和 $M (1 \leq M \leq 100.041)$（虫洞数量）。接下来的 $M$ 行每行包含三个数字 $U, V (1 \leq U \neq V \leq N)$ 和 $W (1 \leq W \leq 100.000)$，表示存在一条连接行星 $U$ 和 $V$ 的虫洞，其修复成本为 $W$。

Output two numbers, the smallest possible cost of entire reparation and the number of different valid reparations with that cost modulo $1000000007$.

输出两个数：整个修复过程的最小可能成本，以及达到该成本的不同有效修复方案的数量（对 $1000000007$ 取模）。

We can repair wormholes $1$,$2$,$3$,$5$ and $6$, paying $5 \oplus 1\oplus 2 \oplus 3 \oplus 4=1$, one can check that this is the cheapest repair in which all of the planets are connected and the only valid repair with that cost.

我们可以修复虫洞 $1$、$2$、$3$、$5$ 和 $6$，花费为 $5 \oplus 1\oplus 2 \oplus 3 \oplus 4=1$；可以验证，这是使所有行星均连通的最便宜的修复方案，且也是唯一具有该花费的有效修复方案。