#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;
const int N = 1e5;
const int M = 2e5;
const int L = 30;

    int n, m;

struct Edge{
    int to, nxt, w;
}e[M * 2 + 3];
    int etop, h[N + 3];

void adde(int u, int v, int w){
    etop++;
    e[etop].to = v;
    e[etop].nxt = h[u];
    e[etop].w = w;
    h[u] = etop;
}

    bool vis[N + 3];
    int s[N + 3];           //presum xor of node i
    int c[L + 3];           //count of s[]' bin digit being 1
    int tot;                //count of connecting block
    LL ans;

void dfs(int u, int fr){
    for(int tmp = h[u], v, news; tmp != -1; tmp = e[tmp].nxt){
        v = e[tmp].to;
        if(v == fr)
            continue;
        
        news = s[u] ^ e[tmp].w;
        
        if(vis[v]){
            if(s[v] != news){
                printf("-1");
                exit(0);
            }
        }
        else {
            vis[v] = true;
            s[v] = news;
            tot++;

            for(int i = 0; i < L; i++)
                if((s[v] >> i) & 1)
                    c[i]++;

            dfs(v, u);
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);

    etop = 0;
    memset(h, -1, sizeof h);
    for(int i = 1, u, v, w; i <= m; i++){
        scanf("%d%d%d", &u, &v, &w);
        adde(u, v, w);
        adde(v, u, w);
    }

    memset(vis, 0, sizeof vis);
    ans = 0;
    for(int i = 1; i <= n; i++)
    if(!vis[i]){
        vis[i] = true;
        s[i] = 0;
        memset(c, 0, sizeof c);
        tot = 1;
        dfs(i, 0);

        // printf("s:");
        // for(int j = 1; j <= n; j++)
        //     printf("%4d", s[j]);
        // printf("\n");
        // printf("c:");
        // for(int j = 0; j < 5; j++)
        //     printf("%3d", c[j]);
        // printf("\n");
        // printf("tot=%d\n", tot);
        // printf("ans=%lld=>", ans);

        for(int j = 0, t = 1; j < L; j++, t <<= 1){
            ans += (LL)min(c[j], tot - c[j]) * t;
        }

        // printf("%lld\n\n", ans);
    }

    printf("%lld", ans);

    return 0;
}