HZNUOJ

生成树

Tags:
Time Limit:  2 s      Memory Limit:   256 MB
Submission:117     AC:40     Score:100.00

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

input
3 4 2 1 2 1 1 3 6 1 3 4 3 2 2
output
8
input
3 2 2 1 2 1 2 3 2
output
-1

Hint

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

Author

ZHANG, Kaili