#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 1e5+10;
i64 res;
struct Bipartite_graph {
    int n;
    vector<pair<int,int> > gra[N];
    int col[N];
    int w;

    void init(int x) {
        n = x;
    }

    void add_edge(int u, int v,int op) {
        gra[u].emplace_back(v,op);
        gra[v].emplace_back(u,op);
    }
    int num1;
    int num2;

    bool dfs(int x) {
        if(col[x]==1)num1++;
        else num2++;
        for (auto& [y,op] : gra[x]) {
            if (!col[y]) {
                if(op)col[y] = -col[x];
                else col[y]=col[x];
                if (!dfs(y))return false;
            }
            else if (col[y] == col[x]&&op)
                return false;
            else if(col[x]==-col[y]&&!op)
                return false;
        }
        return true;
    }


    bool work() {
        for (int i = 1; i <= n; i++) {
            if (!col[i]) {
                num1 = 0;
                num2 = 0;
                col[i] = 1;
                if (dfs(i)) {
                    res += 1LL * min(num1,num2) * w;
                }
                else return false;
            }
        }
        return true;
    }
}gra[31];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i <= 30; i++) {
        gra[i].init(n);
        gra[i].w = (1<<i);
    }


    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        for (int j = 30; j >= 0; j--) {
            if (w & (1 << j)) {
                gra[j].add_edge(u, v,1);
            }
            else gra[j].add_edge(u,v,0);
        }
    }

    for (int i = 30; i >= 0; i--) {
        if (!gra[i].work()) {
            cout << -1 << '\n';
            return 0;
        }
    }

    cout << res;
}