// #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
#define int long long
#define mem(a, b) memset((a), (b), sizeof(a))
#define all(a) (a).begin(), (a).end()
#define lowbit(x) (-x) & x
#define debug cout<<"$"
#define ls u << 1
#define rs u << 1 | 1
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using pi = pair<int,int>;
using p3 = tuple<int,int,int>;
mt19937 rnd(time(0));
const int MOD = 1e9+7;
const ld eps = 1;
int qmi(int m, int k){int res = 1, t = m;while (k){if (k & 1) res = (res * t) % MOD;t = t * t % MOD;k >>= 1;}return res;}
const int N = 2e6 + 7;
const int inf = 1e18 + 7;
int res[6];

void solve()
{
    int n,m;
    cin>>n>>m;
    vector g(n+1,vector<array<int,2>>());
    vector<int> st(n+1);
    vector<int> vis(n+1);
    auto get_hash = [](vector<int> &s)
    {
        const int P = 131;
        auto n = s.size();
        auto h = vector<u128> (n+1);
        auto p = vector<u128> (n+1);
        p[0] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            h[i] = h[i - 1] * P + s[i-1];
            p[i] = p[i - 1] * P;
        }
        return h[n];
    };
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    vector<int> p;
    auto dfs2 = [&] (auto&& self,int u, int co)->void
    {
        vis[u] = 1;
        for(auto [c,d]:g[u])    if(d==co&&!vis[c]&&st[c])
            self(self,c,co);
    };
    map<u128,bool> ma;
    auto dfs = [&] (auto &&self, int u, int dep)->void
    {
        st[u] = 1;
        auto z = p;
        sort(all(z));
        auto ha = get_hash(z);
        if(!ma.count(ha))
        {
            int f = 1;
            for(auto c:p)   vis[c] = 0; dfs2(dfs2,p[0],0);
            for(auto c:p)   if(!vis[c]) f = 0;
            for(auto c:p)   vis[c] = 0; dfs2(dfs2,p[0],1);
            for(auto c:p)   if(!vis[c]) f = 0;
            ma[ha] = f;
        }
        if(dep <= min(n,5ll))
        for(auto [v,c]:g[u]) if(!st[v])
        {
            p.push_back(v);
            self(self,v,dep+1);
            p.pop_back();
        }
        st[u] = 0;
    };
    for(int i=1;i<=n;i++)
    {
        p.push_back(i);
        dfs(dfs,i,1);
        p.pop_back();
    }
    int ans = 0;
    for(auto [c,d]:ma)
        ans += d;
    cout<<ans<<"\n";
}   
signed main()
{
    // freopen("test.in","r",stdin);
    // freopen("test.in","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin>>T;
    while (T--)
        solve();
}
/*
*/