#include <bits/stdc++.h>
using namespace std;

using ll=long long;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using P=pair<int,int>;
using vi=vc<int>;

struct UF {
	vc<int> par,rank;

	void init(int n) {
		par.resize(n+2);
		rank.resize(n+2);
		for(int i=0;i<n;i++) {
			par[i]=i;
			rank[i]=0;
		}
	}
	void reset(int x){
		par[x]=x;
		rank[x]=0;
	}
	int find(int x) {
		if(x==par[x]) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y) {
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else {
			par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	bool same(int x,int y) {
		return find(x)==find(y);
	}
}uf;

void solve(){
	int n,m;
	cin>>n>>m;
	vc<vc<int>> vec[2];
	for(int i=0;i<2;i++) vec[i].resize(n);
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		vec[c][a].pb(b);
		vec[c][b].pb(a);
	}
	uf.init(n+2);
	vc<int> table(n);
	set<vc<int>> st;
	auto check=[&](vc<int> nd)->bool{
		for(int t=0;t<2;t++){
			for(int i=0;i<nd.size();i++){
				uf.reset(nd[i]);
				table[nd[i]]=1;
			}
			for(int i=0;i<nd.size();i++){
				int v=nd[i];
				for(int j=0;j<vec[t][v].size();j++){
					int to=vec[t][v][j];
					if(table[to]){
						uf.unite(to,v);
					}
				}
			}
			for(int i=0;i<nd.size();i++) table[nd[i]]=0;
			for(int i=0;i<nd.size();i++){
				if(!uf.same(nd[0],nd[i])) return false;
			}
		}
		sort(nd.begin(),nd.end());
		if(st.find(nd)==st.end()){
			st.insert(nd);
			return true;
		}
		return false;
	};
	int ret=0;
	for(int i=0;i<n;i++){
		st.clear();
		vc<int> dat;
		dat.pb(i);
		if(check(dat)) ret++;
		for(int j=0;j<vec[0][i].size();j++){
			int to=vec[0][i][j];
			if(to>i){
				dat.pb(to);
				if(check(dat)) ret++;
				for(int k=0;k<vec[1][i].size();k++){
					int u=vec[1][i][k];
					if(u!=to&&u>i){
						dat.pb(u);
						if(check(dat)) ret++;
						for(int l=0;l<vec[0][to].size();l++){
							int v=vec[0][to][l];
							if(v!=u&&v>i){
								dat.pb(v);
								if(check(dat)) ret++;
								dat.pop_back();
							}
						}
						for(int l=0;l<vec[1][to].size();l++){
							int v=vec[1][to][l];
							if(v!=u&&v>i){
								dat.pb(v);
								if(check(dat)) ret++;
								dat.pop_back();
							}
						}
						dat.pop_back();
					}
				}
				dat.pop_back();
			}
		}
	}
	cout<<ret<<endl;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int T=1;
	while(T--) solve();
}