#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<'\n'
#define eb emplace_back
using namespace std;
using ll = long long;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
const int N = 1e5 + 5, MOD = 1e9 + 7;
int n, m;
ll ans, a[N], c[N][32];
vector <pii> e[N][32];
vector <int> vis;
bool dfs(int u,int bit,int fa)
{
    vis.push_back(u);
    for(auto son:e[u][bit])
    {
        int v = son.first, w = son.second;
        if(v!=fa)
        {
            if(c[v][bit]==-1)
            {
                if(w) c[v][bit] = (!c[u][bit]);
                else c[v][bit] = c[u][bit];
                if(!dfs(v,bit,u)) return false;
            }
            else if((c[v][bit]^c[u][bit])!=w) return false;
        }
    }
    return true;
}
void solve()
{
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++)
    {
        cin>>u>>v>>w;
        for(int j=0;j<=30;j++)
        {
            e[u][j].eb(v,(w>>j)&1);
            e[v][j].eb(u,(w>>j)&1);
        }
    }
    for(int bit=0;bit<=30;bit++)
    {
        for(int i=1;i<=n;i++) c[i][bit] = -1;
        ll sum = 0;
        for(int i=1;i<=n;i++)
        {
            if(c[i][bit]==-1)
            {
                pll res = {0,0};
                vis.clear();
                c[i][bit] = 0;
                if(!dfs(i,bit,0))
                {
                    cout<<-1;
                    return ;
                }
                for(auto x:vis)
                {
                    res.first += (1ll<<bit)*c[x][bit];
                    c[x][bit] = -1;
                } 
                vis.clear();
                c[i][bit] = 1;
                dfs(i,bit,0);
                for(auto x:vis) res.second += (1<<bit)*c[x][bit];
                sum += min(res.first,res.second);
            }
        }
        ans += sum;
    }
    cout<<ans;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) solve();
    return 0;
}