#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

int n, m;

LL d[N], bin[N], num[];

bool vis[N];

vector<PLI> edge[N];

vector<int> id;

struct Base {

    LL a[];

    int cnt;

    void init() {

        memset(a, , sizeof(a));

        cnt = ;

    }

    void add(LL x) {

        for(int j = ; ~j; j--) {

            if((x >> j) & ) {

                if(!a[j]) {a[j]=x; cnt++; break;}

                else x ^= a[j];

            }

        }

    }

} base;

void dfs(int u, int fa) {

    vis[u] = true;

    id.push_back(u);

    for(int i = ; i < edge[u].size(); i++) {

        int v = edge[u][i].se; LL w = edge[u][i].fi;

        if(v == fa) continue;

        if(vis[v]) {

            base.add(d[u]^d[v]^w);

        } else {

            d[v] = d[u] ^ w;

            dfs(v, u);

        }

    }

}

int main() {

    base.pirnt();

    scanf("%d%d", &n, &m);

    for(int i=bin[]=; i <= n; i++)

        bin[i] = bin[i-] *  % mod;

    for(int i = ; i <= m; i++) {

        int u, v; LL w;

        scanf("%d%d%lld", &u, &v, &w);

        edge[u].push_back(mk(w, v));

        edge[v].push_back(mk(w, u));

    }

    LL ans = ;

    for(int i = ; i <= n; i++) {

        if(!vis[i]) {

            base.init();

            id.clear();

            dfs(i, );

            for(int j = ; j <= ; j++) {

                num[] = , num[] = ;

                for(auto &x : id) {

                    num[(d[x]>>j)&]++;

                }

                bool flag = false;

                for(int k = ; k < ; k++) {

                    if((base.a[k]>>j)&) {

                        flag = true;

                        break;

                    }

                }

                LL tmp = num[]*(num[]-)/ + num[]*(num[]-)/;

                tmp %= mod;

                if(flag) ans = (ans + bin[j]*bin[base.cnt-]%mod*tmp%mod) % mod;

                tmp = num[] * num[] % mod;

                if(flag) ans = (ans + bin[j]*bin[base.cnt-]%mod*tmp%mod) % mod;

                else ans = (ans + bin[j]*bin[base.cnt]%mod*tmp%mod) % mod;

            }

        }

    }

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

    return ;

}

/*

*/