#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<ll,ll>;
#define x first
#define y second
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
constexpr ll mod=1e9+7,INF=1e18,N=2e5+10;
constexpr ld eps=1e-5;

ll n,m;
vector<pii> g[N];
vector<ll> edge[N],son[N];
bool st[N],md[N],p[N];

struct Graph{
    vector<ll> Node;
    bool operator<(const Graph &x) const{
        return Node<x.Node;
    }

    void dfs(ll u,ll op){
        st[u]=1;
        for(auto x:g[u]){
            ll v=x.first,c=x.second;
            if(c!=op||!md[v]) continue;
            if(st[v]) continue;
            dfs(v,op);
        }
    }

    bool check(){
        bool f=1;
        for(auto x:Node) st[x]=0,md[x]=1;
        
        dfs(Node[0],0);
        for(auto x:Node){
            if(!st[x]){
                f=0;
                break;
            }
        }
        for(auto x:Node) st[x]=0;
        dfs(Node[0],1);

        for(auto x:Node){
            if(!st[x]){
                f=0;
                break;
            }
        }

        for(auto x:Node) md[x]=0;
        return f;
    }
    void sor(){
        sort(Node.begin(),Node.end());
    }
    void clea(){
        Node.clear();
    }
};

set<Graph> q;
ll c=0;
void find(ll u){
    p[u]=1;
    for(auto v:edge[u]){
        if(p[v]) continue;
        son[u].push_back(v);
        find(v);
    }
}
Graph dlt;

void dfs(ll u){
    p[u]=1;
    // len=2;
    for(auto x:son[u]){
        dlt.Node.push_back(u),dlt.Node.push_back(x);
        dlt.sor();
        q.insert(dlt);
        dlt.clea();
    }
    // len=3;
    for(auto x1:son[u]){
        for(auto x2:son[x1]){
            dlt.Node.push_back(u),dlt.Node.push_back(x1),dlt.Node.push_back(x2);
            dlt.sor();
            q.insert(dlt);
            dlt.clea();
        }
    }
    for(int i=0;i<son[u].size();i++){
        for(int j=i+1;j<son[u].size();j++){
            dlt.Node.push_back(u),dlt.Node.push_back(son[u][i]),dlt.Node.push_back(son[u][j]);
            dlt.sor();
            q.insert(dlt);
            dlt.clea();
        }
    }
    // len=4;
    for(int i=0;i<son[u].size();i++){
        for(int j=i+1;j<son[u].size();j++){
            for(int k=j+1;k<son[u].size();k++){
                dlt.Node.push_back(u),dlt.Node.push_back(son[u][i]),dlt.Node.push_back(son[u][j]),dlt.Node.push_back(son[u][k]);
                dlt.sor();
                q.insert(dlt);
                dlt.clea();
            }
        }
    }
    for(int i=0;i<son[u].size();i++){
        for(int j=i+1;j<son[u].size();j++){
            for(auto x:son[son[u][j]]){
                dlt.Node.push_back(u),dlt.Node.push_back(son[u][i]),dlt.Node.push_back(son[u][j]),dlt.Node.push_back(x);
                dlt.sor();
                q.insert(dlt);
                dlt.clea();
            }
        }
    }

    for(int i=0;i<son[u].size();i++){
        for(int j=i+1;j<son[u].size();j++){
            for(auto x:son[son[u][i]]){
                dlt.Node.push_back(u),dlt.Node.push_back(son[u][i]),dlt.Node.push_back(son[u][j]),dlt.Node.push_back(x);
                dlt.sor();
                q.insert(dlt);
                dlt.clea();
            }
        }
    }

    for(auto x1:son[u]){
        for(auto x2:son[x1]){
            for(auto x3:son[x2]){
                dlt.Node.push_back(u),dlt.Node.push_back(x1),dlt.Node.push_back(x2),dlt.Node.push_back(x3);
                dlt.sor();
                q.insert(dlt);
                dlt.clea();
            }
        }
    }

    for(auto v:edge[u]){
        if(p[v]) continue;
        dfs(v);
    }
}

void solve(){
    cin>>n>>m;
    ll u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w}),g[v].push_back({u,w});
        edge[u].push_back(v),edge[v].push_back(u);
    }

    for(int i=1;i<=n;i++){
        sort(edge[i].begin(),edge[i].end());
        edge[i].erase(unique(edge[i].begin(),edge[i].end()),edge[i].end());
    }
    find(1);
    for(int i=1;i<=n;i++) p[i]=0;
    dfs(1);
    
    ll ans=n;
    for(auto x:q) ans+=x.check();
    cout<<ans<<'\n';
}


int main(){
    IOS;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
3 4
1 2 0
1 3 1
2 3 0
2 3 1


4 10
1 2 0
2 3 0
3 4 0
1 4 1
2 4 1
1 3 1
1 2 0
1 3 1
2 3 0
2 3 1

4 6
1 2 0
1 2 1
2 4 1
1 3 0
3 4 0
3 4 1

*/