#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
vector<int> e[2][N];
vector<int> v;
set<vector<int> > ss;
int ans;
int fa[N];
int getfa(int x)
{
    return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y)
{
    x=getfa(x);
    y=getfa(y);
    if (x!=y)
        fa[x]=y;
}
void check()
{
    for (int i=0;i<v.size();++i)    
        for (int j=i+1;j<v.size();++j)
            if (v[i]==v[j])
                return;
    vector<int> vv;
    for (int x:v)
        vv.push_back(x);
    sort(vv.begin(),vv.end());
    if (ss.find(vv)==ss.end())
        ss.insert(vv);
    else
        return;
    for (int x:v)
        fa[x]=x;
    for (int x:v)
        for (int y:e[1][x])
            if (fa[y]!=0)
                merge(x,y);
    set<int> s;
    for (int x:v)
    {
        fa[x]=getfa(x);
        s.insert(fa[x]);
    }
    if (s.size()==1)
        ++ans;
    for (int x:v)
        fa[x]=0;
}
inline void work(int x)
{
    if (e[0][x].size()==3||e[0][x].size()==0)
        return;
    v.clear();
    v.push_back(x);
    for (int y:e[0][x])
        if (y>x)
        {
            v.push_back(y);
            check();
            v.pop_back();
        }
    if (e[0][x].size()==2)
    {
        v.push_back(e[0][x][0]);
        v.push_back(e[0][x][1]);
        bool b=true;
        for (int y:e[0][e[0][x][0]])
            if (y==e[0][x][1])
                b=false;
        if (b||(x<e[0][x][0]&&x<e[0][x][1]))
            check();
        for (int i=0;i<=1;++i)
            if (e[0][x][i]>x&&(int)e[0][e[0][x][i]].size()==2)
            {
                int z=x;
                for (int o:e[0][e[0][x][i]])
                    z^=o;
                v.push_back(z);
                check();
                v.pop_back();
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0,u,v,w;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[w][u].push_back(v);
        e[w][v].push_back(u);
    }
    ans=n;
    for (int i=1;i<=n;++i)
        work(i);
    cout<<ans<<endl;
    return 0;
}