Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int mod = 1000000009;
int main() {
	int N, M;
	cin >> N >> M;
	int lim = max(N, 3);
	vector<int> fact(3 * lim + 1), inv(3 * lim + 1), factinv(3 * lim + 1), val(N + 1);
	fact[0] = 1; inv[1] = 1; factinv[0] = 1;
	for (int i = 1; i <= 3 * lim; ++i) fact[i] = (long long)(fact[i - 1]) * i % mod;
	for (int i = 2; i <= 3 * lim; ++i) inv[i] = (long long)(inv[mod % i]) * (mod - mod / i) % mod;
	for (int i = 1; i <= 3 * lim; ++i) factinv[i] = (long long)(factinv[i - 1]) * inv[i] % mod;
	val[0] = 1; int mul = 1;
	for (int i = 1; i <= N; ++i) {
		mul = (long long)(mul) * factinv[3] % mod;
		val[i] = (long long)(mul) * fact[3 * i] % mod * factinv[i] % mod;
	}
	vector<int> A(M), B(M), C(M);
	vector<int> cv;
	for (int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i] >> C[i];
		cv.push_back(A[i]);
		cv.push_back(B[i]);
	}
	sort(cv.begin(), cv.end());
	cv.erase(unique(cv.begin(), cv.end()), cv.end());
	int S = cv.size();
	vector<int> par(S);
	for (int i = 0; i < S; ++i) par[i] = i;
	function<int(int)> root = [&](int x) {
		if (x == par[x]) return x;
		return par[x] = root(par[x]);
	};
	for (int i = 0; i < M; ++i) {
		A[i] = find(cv.begin(), cv.end(), A[i]) - cv.begin();
		B[i] = find(cv.begin(), cv.end(), B[i]) - cv.begin();
	}
	vector<int> nA, nB;
	for (int i = 0; i < M; ++i) {
		if (C[i] == 0) {
			par[root(A[i])] = root(B[i]);
		}
		else {
			nA.push_back(A[i]);
			nB.push_back(B[i]);
		}
	}
	A = nA; B = nB;
	M = A.size();
	vector<int> inipar = par;
	int ans = 0;
	for (int i = 0; i < 1 << M; ++i) {
		par = inipar;
		int cnt = 0;
		for (int j = 0; j < M; ++j) {
			if ((i >> j) & 1) {
				par[root(A[j])] = root(B[j]);
				++cnt;
			}
		}
		vector<int> hist(S);
		for (int j = 0; j < S; ++j) {
			++hist[root(j)];
		}
		bool ok = true;
		int c1 = 3 * N - S, c2 = 0, c3 = 0;
		for (int j = 0; j < S; ++j) {
			if (hist[j] >= 4) {
				ok = false;
				break;
			}
			if (hist[j] == 3) ++c3;
			if (hist[j] == 2) ++c2;
			if (hist[j] == 1) ++c1;
		}
		if (!ok || c1 < c2) continue;
		int s1 = (c1 - c2) / 3, s2 = c2, s3 = c3;
		int sub = (long long)(fact[c1]) * factinv[c1 - c2] % mod * val[s1] % mod;
		if (cnt % 2 == 0) ans = (ans + sub) % mod;
		else ans = (ans - sub + mod) % mod;
	}
	cout << ans << endl;
	return 0;
}
