Description

一天，小王正在构造一个非负序列a1,a2......an,恰好他的好朋友OceanCat路过。OceanCat觉得仅仅构造非负序列太简单了，于是给小王构造的序列做出了m个限制：au⊕av =w。众所周知，小王成天摸鱼已经很久没有接触算法竞赛了，这个限制可把他愁坏了。于是，小王找到了聪明的你，而且小王还希望构造出来的序列和最小（有可能构造不出来，输出-1），请你帮帮他。

（⊕代表异或）

Input Format

第一行包含两个正整数n(1≤n≤100000),m(1≤m≤200000)表明序列长度为n并且有m个限制。

接下来的m行每行包含三个数字u,v(1≤u,v≤n),w(0≤w≤ 2​^30​)表明给出的限制条件au⊕av =w。

Output Format

如果可以构造出来最小的序列，那么输出序列元素的和。如果不能构造出来，输出-1。

3 2
1 2 1
2 3 1​

1