Example

Input

2 2
1 2 0
3 4 1


Output

2
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
using ll = long long int;
const ll MOD = 1000000009;

// Union-Find 木 (Verified: AtCoder Typical Contest 001 B)
struct UnionFind {
private:
    const int n;
    int size_;
    vector<int> uf;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), size_(_n), uf(_n, -1) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return size_;}
    // x と y の属する集合を併合
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        size_--;
        if(-uf[x] < -uf[y]) swap(x, y);
        uf[x] += uf[y]; uf[y] = x;
        return true;
    }
};

ll mod_pow(ll n, ll k) {
    ll res = 1;
    for(; k>0; k>>=1) {
        if(k & 1) (res *= n) %= MOD;
        (n *= n) %= MOD;
    }
    return res;
}

const int MAXN = 4000010;
ll fact[MAXN+5], finv[MAXN+5];

void init() {
    fact[0] = 1;
    for(int i=1; i<=MAXN; i++) fact[i] = fact[i-1] * i % MOD;

    finv[MAXN] = mod_pow(fact[MAXN], MOD-2);
    for(int i=MAXN-1; i>=0; i--) finv[i] = finv[i+1] * (i+1) % MOD;
}

ll nPr(int n, int r) {
    if(n < r or r < 0) return 0;
    return fact[n] * finv[n-r] % MOD;
}

ll make_group(ll n) {
    ll g = n / 3;
    ll inv = mod_pow(mod_pow(6, g), MOD-2);
    return fact[n] * inv % MOD * finv[g] % MOD;
}

int main() {
    init();
    ll N, M; cin >> N >> M;
    vector< pair<int, int> > good, bad;

    map<int, int> cmp;
    for(int i=0; i<M; i++) {
        int a, b, c; cin >> a >> b >> c; a--; b--;
        (c == 0 ? good : bad).emplace_back(a, b);
        cmp[a]++; cmp[b]++;
    }

    int K = 0;
    for(auto &e : cmp) e.second = K++;

    for(auto &e : good) e.first = cmp[e.first], e.second = cmp[e.second];
    for(auto &e : bad ) e.first = cmp[e.first], e.second = cmp[e.second];
    
    UnionFind uf(K);
    for(auto e : good) {
        int a, b; tie(a, b) = e;
        uf.unite(a, b);
    }

    ll ans = 0;
    vector<bool> used(K);
    for(int bit=0; bit<(1<<(int)bad.size()); bit++) {
        fill(used.begin(), used.end(), false);
        UnionFind uf_c = uf;
        for(size_t i=0; i<bad.size(); i++) {
            if(!(bit >> i & 1)) continue;
            int a, b; tie(a, b) = bad[i];
            uf_c.unite(a, b);
        }

        int cnt[5] = {};
        cnt[1] = 3*N - K;
        for(int i=0; i<K; i++) {
            if(used[ uf_c.find(i) ]) continue;
            used[ uf_c.find(i) ] = true;
            int sz = uf_c.size(i);
            cnt[min(4, sz)]++;
        }

        if(cnt[4] > 0 or cnt[1] < cnt[2]) continue;

        ll add = 1;
        
        // 1 人を、2 人グループにいれる (cnt[1] P cnt[2])
        (add *= nPr(cnt[1], cnt[2])) %= MOD;
        cnt[1] -= cnt[2];

        // 1 人のひとたちで 3 人グループにする
        (add *= make_group(cnt[1])) %= MOD;

        // fprintf(stderr, "add = %lld\n", add);
        
        // 包除原理
        if(__builtin_parity(bit)) ans = (ans - add + MOD) % MOD;
        else ans = (ans + add) % MOD;
    }
    cout << ans << endl;
    return 0;
}

