Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#454. 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$ 且至少存在一棵生成树。