Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <cstdio>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define inver(a) power(a, mod - 2)
using namespace std;
inline char nc() {
	return getchar();
	static char buf[100000], *l = buf, *r = buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x) {
	x = 0; int f = 1, ch = nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x *= f;
}
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 9;
const int maxn = 1e6 + 5;
int n, m;
int an;
int tim;
int f[maxn];
int cnt[maxn * 3];
int fac[maxn * 3];
int inv[maxn * 3];
int vis[maxn * 3];
vector<pii> r[2];
ll power(ll x, ll y) {
	ll re = 1;
	while(y) {
		if(y & 1) re = re * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return re;
}
inline ll binom(int x, int y) {
	return (ll)fac[x] * inv[y] % mod * inv[x - y] % mod;
}
namespace us {
	int fa[maxn * 3];
	void init(int x) {
		fa[x] = x;
	}
	int find(int a) {
		return fa[a] == a ? a : fa[a] = find(fa[a]);
	}
	bool merge(int a, int b) {
		a = find(a);
		b = find(b);
		if(a == b) return 0;
		fa[a] = b; return 1;
	}
}
bool update(int &n, int &a, int x) {
	if(vis[x] == tim) return 0; else vis[x] = tim;
	x = us :: find(x);
	if(++cnt[x] > 3) return 1;
	if(cnt[x] == 3) --a, --n;
	if(cnt[x] == 2) ++a;
	return 0;
}
int cal() {
	++tim;
	for(unsigned int i = 0; i < r[0].size(); ++i) {
		us :: init(r[0][i].fi), cnt[r[0][i].fi] = 0;
		us :: init(r[0][i].se), cnt[r[0][i].se] = 0;
	} 
	for(unsigned int i = 0; i < r[0].size(); ++i) {
		us :: merge(r[0][i].fi, r[0][i].se);
	}
	int a = 0, N = n;
	for(unsigned int i = 0; i < r[0].size(); ++i){
		if(update(N, a, r[0][i].fi)) return 0;
		if(update(N, a, r[0][i].se)) return 0;
	} 
	return binom(N * 3 - a * 2, a) * fac[a] % mod * f[N - a] % mod * inv[N - a] % mod;
}
void dfs(int step, int f) {
	if(step == m) {
		an = (an + (ll)cal() * f) % mod;
		return;
	}
	dfs(step + 1, f);
	r[0].push_back(r[1][step]);
	dfs(step + 1, mod - f);
	r[0].pop_back();
}
void init(int n) {
	int N = n * 3;
	fac[0] = 1;
	for(int i = 1; i <= N; ++i) {
		fac[i] = (ll)fac[i - 1] * i % mod;
	}
	inv[N] = inver(fac[N]);
	for(int i = N; i >= 1; --i) {
		inv[i - 1] = (ll)inv[i] * i % mod;
	}
	f[0] = 1;
	for(int i = 1; i <= n; ++i) {
		f[i] = f[i - 1] * binom(i * 3, 3) % mod;
	}
}
int solve() {
	init(n);
	dfs(0, 1);
	return an;
}
int main() {
//	freopen("in", "r", stdin);
	read(n), read(m);
	for(int i = 1; i <= m; ++i) {
		int a, b, c; read(a), read(b), read(c);
		r[c].push_back(pii(a, b));
	}
	m = r[1].size();
	printf("%d\n", solve());
	return 0;
} 
