Example

Input

2 2
1 2 0
3 4 1


Output

2
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define MOD 1000000009
#define NUM 18
#define SIZE 3000000

struct Info{
	Info(){
		from = 0;
		to = 0;
	}
	Info(int arg_from,int arg_to){
		from = arg_from;
		to = arg_to;
	}
	int from,to;
};

ll N,M;
int connect_num;
int POW[NUM+1];
int good_table[NUM],bad_table[NUM];
ll fact[SIZE+1],dp[SIZE/3+1];
Info info[NUM];
bool visited[SIZE];
vector<int> G[SIZE];


ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll &e){
	e = 0;
	if(n == 0)return 1;

	int res = mod_fact(n/p,p,e);
	e += n/p;

	if(n/p%2 != 0)return res*(p-fact[n%p])%p;
	return res*fact[n%p]%p;
}

ll nCm(ll n,ll m,ll p){
   if(n < m) return 0;
   ll e1,e2,e3;
    ll a1 = mod_fact(n,p,e1),a2 = mod_fact(m,p,e2),a3 = mod_fact(n-m,p,e3);
    if(e1 > e2+e3)return 0;
    return a1 * mod_inverse(a2*a3%p,p)%p;
}

void recursive(int node_id){

	visited[node_id] = true;
	connect_num++;

	for(int i = 0; i < G[node_id].size(); i++){
		if(visited[G[node_id][i]])continue;
		recursive(G[node_id][i]);
	}
}

int main(){

	for(int i = 0; i <= NUM; i++)POW[i] = pow(2,i);

	scanf("%lld %lld",&N,&M);

	fact[0] = 1;
	for(ll i = 1; i <= 3*N; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	dp[0] = 1;
	for(ll i = 1; i <= N; i++){
		dp[i] = nCm(i*3,3,MOD)*dp[i-1];
		dp[i] %= MOD;
	}

	for(int i = 1; i <= N; i++){
		dp[i] *= mod_inverse(fact[i],MOD);
		dp[i] %= MOD;
	}

	int num_good = 0,num_bad = 0;
	int relation;

	for(int i = 0; i < M; i++){

		scanf("%d %d %d",&info[i].from,&info[i].to,&relation);
		info[i].from--;
		info[i].to--;

		if(relation == 0){

			good_table[num_good++] = i;

		}else{

			bad_table[num_bad++] = i;
		}
	}

	ll ans = 0;
	int tmp_bad_count,tmp_index;
	ll num[4],tmp;
	bool FLG;
	queue<int> Q,DEL_Q;

	for(int i = 0; i < 3*N; i++)visited[i] = false;

	for(int state = 0; state < POW[num_bad]; state++){

		tmp_bad_count = 0;
		while(!Q.empty())Q.pop();

		for(int loop = 0; loop < num_good; loop++){

			tmp_index = good_table[loop];
			G[info[tmp_index].from].push_back(info[tmp_index].to);
			G[info[tmp_index].to].push_back(info[tmp_index].from);

			Q.push(info[tmp_index].from);
			Q.push(info[tmp_index].to);

			DEL_Q.push(info[tmp_index].from);
			DEL_Q.push(info[tmp_index].to);
		}

		for(int loop = 0; loop < num_bad; loop++){
			if(state & (1 << loop)){

				tmp_index = bad_table[loop];
				G[info[tmp_index].from].push_back(info[tmp_index].to);
				G[info[tmp_index].to].push_back(info[tmp_index].from);

				Q.push(info[tmp_index].from);
				Q.push(info[tmp_index].to);

				DEL_Q.push(info[tmp_index].from);
				DEL_Q.push(info[tmp_index].to);

				tmp_bad_count++;
			}
		}

		FLG = true;
		for(int i = 1; i <= 3; i++)num[i] = 0;

		while(!Q.empty()){
			tmp_index = Q.front();
			Q.pop();

			if(visited[tmp_index])continue;

			connect_num = 0;
			recursive(tmp_index);

			if(connect_num >= 4){
				FLG = false;
				break;
			}
			num[connect_num]++;
		}

		num[1] = 3*N-2*num[2]-3*num[3];

		if(num[1] < num[2]){
			FLG = false;
		}

		if(FLG){

			tmp = 1;
			for(int i = 0; i < num[2]; i++){
				tmp *= (num[1]-i);
				tmp %= MOD;
			}
			tmp *= dp[(num[1]-num[2])/3];
			tmp %= MOD;

			if(tmp_bad_count%2 == 1){

				ans -= tmp;
				if(ans < 0)ans += MOD;

			}else{

				ans += tmp;
				ans %= MOD;

			}
		}

		while(!DEL_Q.empty()){

			tmp_index = DEL_Q.front();
			DEL_Q.pop();

			G[tmp_index].clear();
			visited[tmp_index] = false;
		}
	}

	printf("%lld\n",ans);

	return 0;
}

