Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define mod 1000000009

int n,m;
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[3000005],R[3000005];
void make(){
	F[0] = 1;
	for(int i=1;i<3000005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<3000005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){ return F[a]*R[b]%mod*R[a-b]%mod; }
vector<P>eq,neq;
int par[3000005],ran[3000005];
void init(){ for(int i=0;i<3000005;i++) par[i] = i,ran[i] = 0; }
int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); }
void unite(int x,int y){
	x = find(x); y = find(y); if(x==y) return;
	if(ran[x] < ran[y]) par[x] = y;
	else{
		par[y] = x;
		if(ran[x] == ran[y]) ran[x]++;
	}
}
bool same(int x,int y){ return find(x)==find(y); }
int main(){
	cin >> n >> m; make();
	for(int i=0;i<m;i++){
		int p,q,a;
		cin >> p >> q >> a;
		if(a == 0) eq.pb(mp(p,q));
		else neq.pb(mp(p,q));
	}
	int x = neq.size();
	ll ret = 0;
	init();
	for(int i=0;i<(1<<x);i++){
		vector<P>E = eq;
		vector<int>vi;
		for(int j=0;j<x;j++){
			if(((i>>j)&1)) E.pb(neq[j]);
		}
		set<int>se;
		map<int,int>ma;
		for(int j=0;j<E.size();j++){
			int s = E[j].fi,t = E[j].sc;
			unite(s,t);
			se.insert(s); se.insert(t);
		}
		int zan = 3*n-se.size();
		for(set<int>::iterator it = se.begin();it != se.end();++it){
			ma[find(*it)]++;
		}
		for(set<int>::iterator it = se.begin();it != se.end();++it){
			par[*it] = *it; ran[*it] = 0;
		}
		ll val = 1;
		for(map<int,int>::iterator it = ma.begin();it !=ma.end();++it){
			if( it->sc > 3) val = 0; assert(it->sc>=2);
			val = val * C(zan,3-it->sc) % mod;
			zan -= (3-it->sc);
		}
		assert(zan%3 == 0); int k = zan/3;
		val = val*F[3*k]%mod;
		val = val*modpow(modpow(6,mod-2),k)%mod*R[k]%mod;
		if(__builtin_popcount(i)%2 == 0) ret = (ret+val)%mod;
		else ret = (ret+mod-val)%mod;
	}
	cout << ret << endl;
}