#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m;
vector<int> Gr[N],Gb[N];
bool del[N];

vector<int> V;
int Id[N],vst[N],usd[N];
inline bool Check(vector<int> V) {
	// printf("V: \n");
	// for(auto i : V) printf("%d ",i);
	// printf("\n");
	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());
	int tt = 0;
	for(auto i : V) Id[i] = ++tt,vst[i] = 0;
	auto dfs0 = [&](const auto &self,int x)->void {
		// printf("dfs0:%d\n",x);
		vst[x] = true;
		for(auto y : Gr[x]) if(!vst[y] && Id[y]) self(self,y);
	};
	dfs0(dfs0,V[0]);
	for(auto i : V) Id[i] = 0;
	for(auto i : V) if(!vst[i]) return false;
	for(auto i : V) vst[i] = 0,Id[i] = ++tt;
	auto dfs1 = [&](const auto &self,int x)->void {
		vst[x] = true;
		for(auto y : Gb[x]) if(!vst[y] && Id[y]) self(self,y);
	};
	dfs1(dfs1,V[0]);
	for(auto i : V) Id[i] = 0;
	for(auto i : V) if(!vst[i]) return false;
	// printf("true\n");
	return true;
}
void dfsr(int x) {
	if(del[x]) return;
	usd[x] = true;V.push_back(x);
	for(auto y : Gr[x])
		if(!usd[y]) dfsr(y);
}
int main() {
	cin >> n >> m;
	for(int i = 1,u,v,c;i <= m;i++) {
		cin >> u >> v >> c;
		if(c == 0) Gr[u].push_back(v),Gr[v].push_back(u);
		else Gb[u].push_back(v),Gb[v].push_back(u);
	}
	for(int i = 1;i <= n;i++) if(!Gr[i].size() || !Gb[i].size()) del[i] = true;
	int ans = 0;
	for(int i = 1;i <= n;i++) if(!del[i] && !usd[i]) {
		V.clear();dfsr(i);
		int siz = V.size();
		for(int i = 0;i < siz;i++) {
			vector<int> now;
			for(int j = i,d = 0;d < siz - 1 && d <= 6;j = (j + 1) % siz,d++)
				now.push_back(V[j]),ans += Check(now);
		}
		if(siz <= 7) ans += Check(V);
	}
	cout << ans << endl;
	return 0;
}