#include<bits/stdc++.h>

using namespace std;

#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 7;
const int N = 1e5 + 50;

ll n, m, p0[N][32], p[N][32], ans = 0;
vector<pll> xt[32], bt[32];

ll find(ll x, ll i)
{
    if (x != p0[x][i]) p0[x][i] = find(p0[x][i], i);
    return p0[x][i];
}

ll vis[N], vs[N], st[N], ok, siz[N], vs0[N], res0, tot, res;
vector<ll> e[N];

void dfs(ll u, ll co, ll k)
{
    if (ok == 1) return ;
    for (auto it : e[u])
    {
        if (ok == 1) return ;
        if (k == 1)
        {
            //if (u == 3) cout << st[u] << st[it] << '\n';
            if (st[it] >= 0 && st[it] != 1 - st[u])
            {
                ok = 1;
                return;
            }
        }
        if (vs0[it] == tot) continue;
        st[it] = 1 - co;
        if (1 - co == 1) res0 += siz[it];
        vs0[it] = tot;
        dfs(it, st[it], k);
    }
}

ll fp[35];

void solve()
{

    for (int i = 0; i <= 30; i++) fp[i] = pow(2, i);
    cin >> n >> m;
    ll u0, v0, w0, cnt = 0;
    vector<ll> v;
    for (int i = 1; i <= m; i++)
    {                                                               
        cin >> u0 >> v0 >> w0;
        v.clear();
        v.push_back(0);
        cnt = 0;
        while (w0 > 0)
        {
            v.push_back(w0 % 2);
            w0 /= 2;
            cnt ++;
        }
        for (int i = 1; i <= cnt; i++) // 第i位
        {
            if (v[i] == 0) xt[i].push_back({u0, v0});
            else bt[i].push_back({u0, v0});
        }
    }
    for (int i = 1; i <= 30; i++)
    {
        for (int i = 0; i <= n + 10; i++)
        {
            vis[i] = vs[i] = siz[i] = vs0[i] = 0;
            st[i] = -1;
            e[i].clear();
        }
        tot = 0;

        if (xt[i].size() == 0 && bt[i].size() == 0) continue;
        for (int j = 0; j <= n + 10; j++)
        {
            p0[j][i] = j;
        }
        for (auto [p, q] : xt[i])
        {
            ll pu = find(p, i), pv = find(q, i);
            if (pu != pv) p0[pv][i] = pu;
        }
        cnt = 0;
        for (int j = 0; j <= n + 10; j++)
        {
            vis[i] = 0;
        }
        for (int j = 1; j <= n; j++)
        {
            if (vis[p0[j][i]] == 0)
            {
                cnt ++;
                vs[p0[j][i]] = cnt;
                p[j][i] = cnt;
                siz[cnt] = 1;
            }
            else 
            {
                p[j][i] = vs[p0[j][i]];
                siz[vs[p0[j][i]]] ++;
            }
        }
        ok = 0;
        for (auto [p1, q1] : bt[i])
        {
            e[p[p1][i]].push_back(p[q1][i]);
            e[p[q1][i]].push_back(p[p1][i]);
            //cout << p[p1][i] << ' ' << p[q1][i] << '\n';
            if (p[p1][i] == p[q1][i])
            {
                ok = 1;
                break;
            }
        }
        if (ok == 1) break;
        for (int j = 1; j <= cnt; j++) st[j] = -1;
        for (int j = 1; j <= cnt; j++)
        {
            if (st[j] == -1)
            {
                res = 1e18; // 1 个数
                res0 = 0;
                tot ++;
                vs0[j] = tot;
                st[j] = 0;
                dfs(j, 0, 1);
                res = min(res, res0);
                //for (int i = 1; i <= n; i++) cout << st[i] << ' ';

                res0 = siz[j];
                tot ++;
                vs0[j] = tot;
                st[j] = 1;
                dfs(j, 1, 2);
                res = min(res, res0);
                ans += res * fp[i - 1];
            }
        }
        


    }
    if (ok == 1) cout << -1;
    else cout << ans;
    
}

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