#include <bits/stdc++.h>

//DEBUG:    https://github.com/sharkdp/dbg-macro
#ifdef LOCAL
#include "../Lib/dbg-macro-0.5.1/dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif

#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double llf;
const ll MAXN=2e5+10,MOD=998244353,INF=1e9;

ll qpow(ll base,ll exp){ll ans=1;while(exp){if(exp&1)(ans*=base)%=MOD;(base*=base)%=MOD;exp>>=1;}return ans;}
template<class T>ll max_binary_answer(ll l,ll r,T check,bool cmp=true){ll m;while(l<r){m=(l+r+1)/2;if(cmp^!check(m))l=m;else r=m-1;}return l;}
template<class T>ll min_binary_answer(ll l,ll r,T check,bool cmp=true){ll m;while(l<r){m=(l+r)/2;if(cmp^!check(m))r=m;else l=m+1;}return r;}
ll exgcd(ll a,ll b,ll &x,ll &y){ll tmp;return b==0?(x=1,y=0,a):(tmp=exgcd(b,a%b,y,x),y-=(a/b)*x,tmp);}
ll highbit(ll x){for(ll i=1;i<(ll)sizeof(ll)*4;i<<=1)x|=x>>i;return x-(x>>1);}
ll lowbit(ll x){return x&(-x);}
//--------Global declared area--------

//--------Global declared end --------
void solve(int test_num){
	int n,m;
	ll sum=0;
	cin>>n>>m;
	vector<vector<pair<ll,ll>>> g(n+1);
	vector<int> vis(n+1),ans(n+1);
	for(int i=0;i<m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	for(int bit=1;bit<(1<<30);bit<<=1){
		queue<int> q;
		fill(vis.begin(),vis.end(),0);
		for(int i=1;i<=n;i++){
			bool flag=true;
			if(!vis[i]){
				q.push(i);
				vis[i]=1;
			}
			while(!q.empty()){
				int p=q.front();
				q.pop();
				for(auto [to,w]:g[p]){
					flag=false;
					if(!vis[to]){
						vis[to]=1;
						q.push(to);
						if(w&bit){
							ans[to]|=(bit^(ans[p]&bit));
						}else{
							ans[to]|=(ans[p]&bit);
						}
					}else{
						if(w&bit){
							if((ans[to]&bit)==(ans[p]&bit)){
								cout<<-1<<endl;
								return;
							}
						}else{
							if((ans[to]&bit)!=(ans[p]&bit)){
								cout<<-1<<endl;
								return;
							}
						}
					}
				}
			}
			if(flag){
				vis[i]=0;
			}
		}
		ll cnt=0,tmp=0;
		for(int i=1;i<=n;i++){
			if(vis[i]){
				cnt++;
				if(ans[i]&bit){
					tmp++;
				}
			}
		}
		sum+=min(tmp*bit,(cnt-tmp)*bit);
	}
	cout<<sum<<endl;
}

int main(){
#ifdef ACM
	freopen("D:/Code/C or C++/File/input.txt","r",stdin);
	freopen("D:/Code/C or C++/File/output.txt","w",stdout);
	freopen("D:/Code/C or C++/File/error.txt","w",stderr);
#else
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr),std::cout.tie(nullptr);
#endif
	int t=1;
//	cin>>t;
	for(int i=1;i<=t;i++){
		solve(i);
		//cout.flush();
	}
	return 0;
}