#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define For(i,a,aa) for(int i=a;i<=aa;i++)
const int N=1e5+7;
int n,m,x,y,w;
int d[N][40];
int yi[40],lin[40];
int p[40],cnt[40];
vector <int> v[N][40];
int mp[N][40];
void solve(){
    int ans=0;
	cin>>n>>m;
    For(i,1,n)
        For(j,1,30)
            d[i][j]=-1;
    For(j,1,30) cnt[j]=0;
    For(i,1,m)
    {
        cin>>x>>y>>w;
        int a[40],tot=0;
        memset(a,0,sizeof(a));
        while(w)
        {
            a[++tot]=w%2;
            w>>=1;
        }
        For(j,tot+1,30) a[j]=0;
        For(j,1,30)
        {
            if(d[x][j]!=-1&&d[y][j]!=-1)
            {
                if(d[x][j]^d[y][j]==0&&a[j]==1) 
                {
                    cout<<-1;return;
                }
                else if(d[x][j]^d[y][j]==1&&a[j]==0) 
                {
                    cout<<-1;return;
                }     
                else 
                {
                    //x,x^1,y,y^1合并
                    if((v[d[y][j]][j].size()+v[d[y][j]^1][j].size())<=(v[d[x][j]][j].size()+v[d[x][j]^1][j].size()))
                    {
                        //For(k,0,v[d[y][j]][j].size()-1) 
                            //v[a[j]^d[x][j]][j].push_back(v[d[y][j]][j][k]),d[v[d[y][j]][j][k]][j]=d[x][j];

                        mp[d[x][j]][j]+=mp[d[y][j]][j];mp[d[y][j]][j]=0;
                        //For(k,0,v[d[y][j]^1][j].size()-1) 
                           // v[a[j]^(d[x][j]^1)][j].push_back(v[d[y][j]^1][j][k]),d[v[d[y][j]^1][j][k]][j]=d[x][j]^1;

                        mp[a[j]^(d[x][j]^1)][j]+=mp[d[y][j]^1][j];mp[d[y][j]^1][j]=0;                       
                    }
                    /*else{
                        For(k,0,v[d[x][j]][j].size()-1) 
                            v[a[j]^d[y][j]][j].push_back(v[d[x][j]][j][k]),d[v[d[x][j]][j][k]][j]=d[y][j];
                        
                        mp[d[x][j]][j]=0;mp[d[y][j]][j]=v[d[x][j]][j].size();
                        For(k,0,v[d[x][j]^1][j].size()-1) 
                            v[a[j]^(d[y][j]^1)][j].push_back(v[d[x][j]^1][j][k]),d[v[d[x][j]^1][j][k]][j]=d[y][j]^1;
                        mp[d[x][j]^1][j]=0;mp[a[j]^(d[y][j]^1)][j]=v[d[x][j]^1][j].size();                          
                    }*/
                }
            }
            else if(d[y][j]==-1&&d[x][j]==-1)
            {
                if(a[j])
                {
                    //v[cnt[j]][j].push_back(x);
                    //v[cnt[j]+1][j].push_back(y);
                    mp[cnt[j]][j]++;
                    mp[cnt[j]+1][j]++;
                    d[x][j]=cnt[j];
                    d[y][j]=cnt[j]+1;    
                    cnt[j]+=2;                      
                }
                else{
                    //v[cnt[j]][j].push_back(x);
                    //v[cnt[j]][j].push_back(y);
                    mp[cnt[j]][j]+=2;
                    d[x][j]=cnt[j];
                    d[y][j]=cnt[j];    
                    cnt[j]+=2;                     
                }
            }
            else if(d[x][j]==-1)
            {
                if(a[j])
                {
                    d[x][j]=d[y][j]^1;mp[d[x][j]][j]++;
                    //v[d[x][j]][j].push_back(x);                    
                }
                else{
                    d[x][j]=d[y][j];mp[d[x][j]][j]++;
                    //v[d[x][j]][j].push_back(x);                      
                }
            }
            else{
                if(a[j])
                {
                    d[y][j]=d[x][j]^1;mp[d[y][j]][j]++;
                    //v[d[y][j]][j].push_back(y);                    
                }
                else
                {
                    d[y][j]=d[x][j];mp[d[y][j]][j]++;
                    //v[d[y][j]][j].push_back(y);                      
                }
            }
        }
    }
	For(j,1,30)
    {
        int tp=0;
        for(int i=0;i<cnt[j];i+=2)
        {
            tp+=min(mp[i][j],mp[i+1][j]);//cout<<v[i][j].size()<<"!"<<v[i+1][j].size()<<"!!"<<endl;
        }
        ans+=p[j]*tp;//cout<<ans<<"!";
        //cout<<cnt[j]<<"!";
    }
    cout<<ans;
}
signed main(){
	fast;
	int t=1;
	//cin>>t;
    p[1]=1;
    For(i,2,30)    p[i]=p[i-1]*2;
	while(t--){
		solve();
	}
}