生成树

Tags:

Description

复习了 $10086$ 遍最小生成树之后，风老板认为最小生成树的东西太简单了，但是他想考验一下队友 $ZKL$ ，于是提出了新的问题。对于一个无向图，给出一个 $x$ ，风老板想让 $ZKL$ 告诉他这个图是否存在一棵生成树，对于树上的每条边权  $a_i$ ，满足 $(a_1 \& a_2 \& ... \& a_n)\& x=x$ (' $\&$ '符号代表按位与运算) , 然而这个问题对于 $ZKL$ 来说太难了，于是 $ZKL$ 向你求助。

Input

第一行三个正整数 $n,m,x$ ，表示有 $n$ 个点，$m$ 条边, $x$ 即上文中给出的数。 $(1\leq n \leq 2 \times 10^5,0\leq m \leq 10^6,0\leq x \leq 10^9)$

接下来 $m$ 行，每行三个正整数 $u,v,w$ ，表示存在一条连通 $u,v$ 的长度为 $w$ 的无向边。$(1\leq u,v \leq n,0\leq w \leq 10^9)$

Output

输出一行一个整数，即满足条件的生成树的边权和，如果存在多颗满足条件的生成树，则输出边权和的最小值。如果不存在满足条件的生成树，则输出" $-1$ "。

Samples

Hint

给出的图可能存在自环和重边。

Author