#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 rng(random_device{}());
int random(int l,int r) {
    return rng()%(r - l + 1) + l;
}
unordered_map <int,int> mp;
struct DSU {
    int n;
    std::vector<int> fa, sz;
    DSU(int n): n(n) {
        fa.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 0; i <= n; i ++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x) {
        if (x == fa[x]) return fa[x];
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        int dx = find(x), dy = find(y);
        if (dx != dy) {
            sz[dy] += sz[dx];
            fa[dx] = dy;
        }
    }
};
signed main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    vector <vector <int>> g1(n + 1);
    vector <vector <int>> g2(n + 1);
    for(int i=1;i<=m;i++) {
        mp[i] = random(1,1e18);
        int u , v , w;
        cin >> u >> v >> w;
        if(w==0) {
            g1[u].push_back(v);
            g1[v].push_back(u);
        }
        else {
            g2[u].push_back(v);
            g2[v].push_back(u);
        }
    }

    DSU dsu(n + 1);
    vector <int> vis(n + 1);
    vector <int> T;
    set <int> all;
    auto check = [&](int x) {
        for(auto i : T) {
            if(x== i) return true;
        }
        return false;
    };
    auto dfs = [&](auto &dfs,int u)->void {
        if(vis[u]) return;
        vis[u] ++ ;
        map <int,int> mpp;
        for(auto i : T) {
           mpp[i] ++ ;
            if(mpp[i]>=2) return;
        }
        // cout << "\n";
        if(T.size() <=4){
            set <int> st;
            for(auto i : T) {
                dsu.fa[i] = i;
            }
            for(auto i : T) {
                for(auto v : g2[i]) {
                    if(check(v)) {
                        dsu.merge(i,v);
                    }

                }
            }
            for(auto i : T) {
                st.insert(dsu.fa[i]);
            }
            // cout << st.size() << "\n";
            if(st.size()==1) {
                int ans = 0;
                for(auto i : T) {
                    ans ^= mp[i];
                }
                all.insert(ans);
            }
            for(auto i : T) {
                for(auto v : g2[i]) {
                    dsu.fa[i] = i;
                    dsu.fa[v] = v;
                }
            }
            // cout << "\n";

        }
        else {
            return;
        }
        for(auto v : g1[u]) {

            T.push_back(v);
            dfs(dfs,v);
            vis[v] -- ;
            T.pop_back();
        }
    };

    for(int i=1;i<=n;i++) {
        T.push_back(i);
        dfs(dfs,i);
        T.pop_back();
    }
    cout << all.size() << "\n";

    return 0;
}