#include<bits/stdc++.h>
#define int long long

using namespace std;

using PII = pair<int,int>;

const int N = 30, M = 2e5 +10;
vector<int> g[N][M];

int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}


signed main()
{
    cin.tie(0), ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> u(m + 1), v(m + 1), w(m + 1);
    vector<vector<PII>> g1(35);
   
    for(int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        for(int j = 0; j < 30; j++)
        {
            if((w[i] >> j) & 1)
            {
                g[j][u[i]].push_back(v[i]);
                g[j][v[i]].push_back(u[i]);
            }
            else
            {
                g1[j].push_back({v[i], u[i]});
            }
        }
    }


    vector<bool> vis(n + 1, false);
    vector<int> col(n + 1, 0);
    int ans = 0;
    auto bfs = [&](int x, int j){
        queue<int> q;
        vis[x] = true;
        q.push(x);
        col[x] = 1;
        vector<int> u;
        while(q.size())
        {
            int t = q.front();
            u.push_back(t);
            q.pop();
            for(auto v : g[j][t])
            {
                if(!col[v])
                {
                    col[v] = (col[t] * 2) % 3;
                    vis[v] = true;
                    q.push(v);
                }
                else
                {
                    if(col[v] == col[t])
                    {
                        return 1;
                    }
                    if(!vis[v])
                    {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        for(auto [x, y] : g1[j])
        {
            if(col[x] && col[y])
            {
                if(col[x] != col[y])
                {
                    cout << -1 << endl;
                    return 0;
                }
            }
            else if(!col[x] && !col[y]) ;
            else
            {
                if(!col[x]) col[x] = col[y];
                else col[y] = col[x];
            }
        }
        int cnt = 0, cnt1 = 0;
        for(int i = 0; i < u.size(); i++)
        {
            if(col[u[i]] == 1) cnt++;
            else cnt1++;
        }
        ans += min(cnt, cnt1) * qmi(2ll, j);
        return 2;
    };
    for(int j = 0; j < 30; j++)
    {
        for(int i = 1; i <= n; i++) vis[i] = false, col[i] = 0;
        for(int i = 1; i <= n; i++)
        {
            if(!vis[i] && g[j][i].size())
            {
                int sum = bfs(i, j);
                if(sum == 1)
                {
                    cout << -1 << endl;
                    return 0;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}