//#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
//#define int long long
const int N = 1e5 + 50;
const int M = 5e5 + 5;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
//random_shuffle(id + 1, id + n + 1);
ll ksm(ll a, ll b);
ll gcd(ll a, ll b);

//感觉数据能到挺大，先到2^50试试，也就是说我们要建50次图

vector<vector<pair<ll, ll> > >e(N);
ll n, m;
ll ans = 0;
vector<vector<pair<ll, ll> > >ee(N);
ll idx = -1;
void build_map() {
	for (int i = 1; i <= n; i++) {
		ee[i].clear();
	}
	for (int i = 1; i <= n; i++) {
		for (auto p = e[i].begin(); p != e[i].end(); p++) {
			ll u = i, v = p->X, w = p->Y;
			if ((w>>idx) & 1) {//建1边
				ee[u].push_back({ v,1 });
			}
			else {
				ee[u].push_back({ v,0 });
			}
		}
	}
}

bool vis[N];
bool dis[N];
void bfs(int s) {
	queue<int>q;
	q.push(s); dis[s] = 0;
	ll a = 0, b = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		if (vis[u])continue;
		if (dis[u] == 0)a++;
		else b++;
		vis[u] = 1;
		for (auto p = ee[u].begin(); p != ee[u].end(); p++) {
			ll v = p->X;
			ll w = p->Y;
			if (vis[v] == 0) {
				if (w == 0) {//两个元素相同
					dis[v] = dis[u];
				}
				else {
					dis[v] = !dis[u];
				}
				q.push(v);
			}
			else {
				if (w == 0) {
					if (dis[u] != dis[v]) {
						cout << -1 << endl;
						exit(0);
					}
				}
				else {
					if (dis[u] == dis[v]) {
						cout << -1 << endl;
						exit(0);
					}
				}
			}
		}
	}
	ans += (1ll << idx) * (min(a, b));
}

void op() {
	for (int i = 1; i <= n; i++) {
		vis[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 0) {
			bfs(i);
		}
	}
}

void solve()
{
	//有两个note，两个元素或运算的值，就是两个元素加起来最小的ans
	//如果两个元素或一个元素得到了相同的ans那么这两个元素是同一个元素
	//对于给出的u,v两个元素，出现次数较少的元素，我们认为是0

	//能建图当图论写吗

	/*
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		ll u, v, w; cin >> u >> v >> w;
		du[u]++; du[v]++;
		live[u] = 1; live[v] = 1;
		e[u].push_back({ v,w });
		e[v].push_back({ u,w });
	}*/
	//会了，一开始我还在想凑出1:1:1..的整个序列，然后除去倍数，如果%不为0 则不合法，否则输出
	//但是我仔细看了看，感觉成环的能判是否合法，直接走的路径直接计算就行，只需要最后加上头尾的异或值，除二就行，应该
	//所以，如果是一条线，a^b^c^d,就是a^b+b^c+c^d,而a+b的最小值就是a^b，b+c的最小值就是b^c
	//所以我们dfs累加a^b,b^c,c^d,然后再加上a^d就得到2*(a+b+c+d)的最小值，除二后就得到ans
	//但是这是一条直线的情况，如果分叉，该怎么办，分叉的位置只能计一次，我们照图的遍历，直接就下去了
	//难，分叉，只需要在向下搜的时候判断是否是第一分支就能避免重复选取
	//但是还有成环的情况，一旦成环，就会向上回溯，向上回溯就会导致计数的重复，想到这里，大概，就不是正解了

	//看到正解了，真是，感觉，有点夸张，首先，两个元素异或，得到了一个数，那个数将对两个元素进行约束
	//就是说，如果在二进制下第k位是1，那么两个元素在第k位必须不同，相对应的，如果在二进制下第k位是0
	//那么两个元素在第k位必须相同，这时候，建立了图，传递的就不再是数值，而是关系
	//这样重叠，交错，成环不再产生影响，他们仅会关联起来，如果两个元素要求在k位的条件冲突，输出-1
	//我们在放置元素的时候不妨假定起始元素为0，遍历图的过程中递推出剩余元素的情况，
	//然后由于01互换依旧合法，我们选择小的情况即可

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		ll u, v, w; cin >> u >> v >> w;
		e[u].push_back({ v,w });
		e[v].push_back({ u,w });
	}


	for (int i = 0; i <= 50; i++) {
		++idx;
		build_map();
		op();
	}

	cout << ans << endl;

	return;
}


signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--)
		solve();
	return 0;
}

/*PonyHex*/


ll ksm(ll a, ll b) {
	ll base = a;
	ll ans = 1;
	while (b) {
		if (b & 1)ans *= base % mod;
		ans %= mod;
		base *= base; base %= mod;
		b >>= 1;
	}
	return ans % mod;
}
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}