Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000009
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,a[20],b[20],c[20],fa[50],dep[50],cnt[50];
ll ans=0,p[3000005],P[3000005],X[1000005],Y[1000005];
vector<int> A,B;
int find(int x){
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void unite(int x,int y){
	x=find(x),y=find(y);
	if (x==y) return ;
	if (dep[x]<dep[y]){
		fa[x]=y;
		return ;
	}
	fa[y]=x;
	if (dep[x]==dep[y])
		dep[x]++;
}
ll solve(){
	memset(cnt,0,sizeof(cnt));
	for (int i=1;i<=45;i++)
		fa[i]=i;
	for (int i=1;i<=m;i++)
		if (!c[i]) unite(a[i],b[i]);
	for (int i=1;i<=45;i++)
		cnt[find(i)]++;
	int c3=0,c2=0;
	for (int i=1;i<=45;i++){
		if (cnt[i]>3) return 0;
		if (cnt[i]==3) c3++;
		if (cnt[i]==2) c2++;
	}
	int c1=3*n-3*c3-2*c2;
	if (c1<c2) return 0;
	ll res=(p[c1]*P[c1-c2])%mod;
	res=(res*p[c1-c2])%mod;
	res=(res*X[(c1-c2)/3])%mod;
	res=(res*Y[(c1-c2)/3])%mod;
	return res;
}
void dfs(int now,int cnt){
	if (now>m){
		if (cnt&1)
			ans=(ans-solve()+mod)%mod;
		else
			ans=(solve()+ans)%mod;
		return ;
	}
	dfs(now+1,cnt);
	if (c[now]){
		c[now]=0;
		dfs(now+1,cnt+1);
		c[now]=1;
	}
}
ll pow(ll x,int y){
	ll res=1;
	while (y){
		if (y&1) res=(res*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return res%mod;
}
int main(){
	p[0]=1;
	n=read(),m=read();
	for (int i=1;i<=3*n;i++)
		p[i]=(p[i-1]*(ll) i)%mod;
	for (int i=max(0,3*n-100);i<=3*n;i++)
		P[i]=pow(p[i],mod-2);
	for (int i=max(0,n-100);i<=n;i++)
		X[i]=pow(p[i],mod-2);
	for (int i=max(0,n-100);i<=n;i++)
		Y[i]=pow(pow((ll) 6,i),mod-2);
	for (int i=1;i<=m;i++)
		a[i]=read(),b[i]=read(),c[i]=read();
	for (int i=1;i<=m;i++)
		A.push_back(a[i]),A.push_back(b[i]);
	sort(A.begin(),A.end());
	A.erase(unique(A.begin(),A.end()),A.end());
	for (int i=1;i<=m;i++){
		a[i]=lower_bound(A.begin(),A.end(),a[i])-A.begin()+1;
		b[i]=lower_bound(A.begin(),A.end(),b[i])-A.begin()+1;
	}
	dfs(1,0);
	printf ("%lld\n",ans);
	return 0;
}