Minimum Or Spanning Tree

题目描述

给出$n$个点， $m$条边的无向图， 每条边连接$u,v$两个端点，边权为$w$， 求图的生成树的最小代价。

在这道题中， 我们定义一棵生成树的代价为他所有边的边权按位或得到的值。

输入格式

第一行两个数字 $n$ 和 $m$ , $n$ 表示点数，$m$ 表示图的边数。

接下来 $m$ 行 , 每行三个整数 $u,v,w$，表示点 $u$ 和点 $v$ 之间存在一条边权为 $w$ 的边。

输出格式

一行， 描述生成树的最小代价。

样例输入

5 7
4 2 7
2 5 8
3 4 2
3 2 1
2 4 2
4 1 2
1 2 2

样例输出

10

数据范围

所有数据保证 $1\leq u,v\leq n\leq 2\cdot 10^5, n-1\leq m \leq 4\cdot 10^5 , 1 \leq w\leq 10^9$ 且至少存在一棵生成树。