Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pr pair<int,int>
#define Rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define debug(x) {cout<<(#x)<<" "<<x<<endl;}

using namespace std;
typedef long long ll;

const int N=40,INF=9999999;
const ll P=1e9+9;

template<typename T>
inline void read(T& x,char s=getchar()) {
	x=0;
	while(s>'9'||s<'0') s=getchar();
	while(s<='9'&&s>='0') x=x*10+s-'0',s=getchar();
}

inline ll _pow(ll a,ll b,ll r=1) {
	while(b) {
		if(b&1) (r*=a)%=P;
		(a*=a)%=P;
		b>>=1;
	}
	return r;
}

vector<pr> a,b;
map<int,int> ma;
int cnt;
int c[N];
int fa[N];
ll js[3000005];
ll fq[3000005];

inline int find(int x) {
	return x==fa[x]?x:fa[x]=find(fa[x]);
}

inline void unionn(int x,int y) {
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) fa[fy]=fx;
}

int main() {
	int n,m,x,y,t;
	ll ans=0;
	cin>>n>>m;
	js[0]=fq[0]=1;
	for(int i=1;i<=3*n;i++) {
		js[i]=js[i-1]*i%P;
		if(i%3==0) {
			fq[i]=fq[i-3]*i*2%P; 
			//if(i<=10) cout<<fq[i]<<" ";
		}
	}
	
	for(int i=1;i<=m;i++) {
		cin>>x>>y>>t;
		if(ma.count(x)) x=ma[x];
		else ma[x]=++cnt,x=cnt;
		if(ma.count(y)) y=ma[y];
		else ma[y]=++cnt,y=cnt;
		
		if(t==0) {
			a.pb(mp(x,y));
		}
		else {
			b.pb(mp(x,y));
		}
	}
	for(int j=0;j<(1<<b.size());j++) {
		ll num=0;
		for(int i=1;i<=cnt;i++) fa[i]=i;
		for(int i=0;i<a.size();i++) {
			unionn(a[i].x,a[i].y);
		}
		for(int i=0;i<b.size();i++) {
			if(j&(1<<i)) {
				num++;
				unionn(b[i].x,b[i].y);
			}
		}
//		cout<<"num: "<<j<<" "<<num<<endl;
		num=num&1?-1:1;
		
//		cout<<num<<": ";
		memset(c,0,sizeof(c));
		for(int i=1;i<=cnt;i++) {
			c[find(i)]++;
		}
		int _n=n;
		int qindian=0;
		ll tot=1;
		for(int i=1;i<=cnt;i++) {
//			cout<<c[i]<<" ";
			if(c[i]>3) {
				tot=0;
//				cout<<endl;
				break;
			}
			if(c[i]==3) _n--;
			if(c[i]==2) qindian++;
		}
//		cout<<endl;
		
		if(tot==0) continue;
		
//		ll test=_pow(6,P-2)*6%P;
//		cout<<"-==>"<<test<<endl;
		
		tot=js[_n*3-qindian*2]*_pow(js[_n*3-qindian*3],P-2)%P;
//		cout<<"-->"<<_n*3-qindian*2<<" "<<_n*3-qindian*3<<endl;
//		cout<<"-->"<<js[_n*3-qindian*2]<<" "<<js[_n*3-qindian*3]<<endl;
//		cout<<"-->"<<tot<<endl;
		_n-=qindian;
//		cout<<"__n: "<<_n<<endl;
		tot=tot*js[_n*3]%P*_pow(fq[_n*3],P-2)%P;
//		cout<<"-->"<<tot<<endl;
		ans=(ans+P+num*tot)%P;
	}
	cout<<ans<<endl;
	return 0;
}
/*
2 3
1 2 0
3 5 0
3 4 1

2 2
1 2 0
3 4 1

10003 2
1 2 0
3 4 1
*/