Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+9;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=3000005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

int n,m;
vi a,b;
vi c,d;

int main(){
	Init();
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		if(w==0){
			a.push_back(u);
			b.push_back(v);
		}
		else{
			c.push_back(u);
			d.push_back(v);
		}
	}
	int sa=a.size(),sc=c.size();
	ll res=0;
	for(int i=0;i<1<<sc;i++){
		vi s=a,t=b,e;
		int tmp=0;
		for(int j=0;j<sc;j++) if(i&1<<j){
			s.push_back(c[j]);
			t.push_back(d[j]);
			tmp++;
		}
		m=s.size();
		for(int j=0;j<m;j++){
			e.push_back(s[j]);
			e.push_back(t[j]);
		}
		sort(e.begin(),e.end());
		e.erase(unique(e.begin(),e.end()),e.end());
		map<int,int> mp;
		int N=e.size();
		for(int j=0;j<N;j++) mp[e[j]]=j;
		vvi g(N);
		for(int j=0;j<m;j++){
			int u=mp[s[j]],v=mp[t[j]];
			g[u].push_back(v);
			g[v].push_back(u);
		}
		vi used(N);
		int x=3*n-N,y=0,z=0;
		bool B=0;
		for(int i=0;i<N;i++) if(!used[i]){
			int t=0;
			queue<int> q;
			q.push(i);
			used[i]++;
			int cnt=0;
			while(!q.empty()){
				int v=q.front();q.pop();
				cnt++;
				for(auto u:g[v]) if(!used[u]){
					used[u]++;
					q.push(u);
				}
			}
			if(cnt>3) B=1;
			if(cnt==2) y++;
			if(cnt==3) z++;
		}
		if(B||y>x) continue;
		ll ei=nCk(x,y)*F[y]%mod*Div(F[x-y],Pow(6,(x-y)/3)*F[(x-y)/3]%mod)%mod;
		if(tmp%2==1) (ei*=mod-1)%=mod;
		(res+=ei)%=mod;
	}
	cout<<res<<endl;
}
