#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

const int mod = 1e9 + 9;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

int qpow(int a, int b){
    int ans = 1;
    while(b){
        if (b & 1) ans = mul(ans, a);
        b >>= 1;
        a = mul(a, a);
    }
    return ans;
}

const int maxn = 3e6 + 5;
int fact[maxn], invfact[maxn];
int powfact3[maxn];

int p[100], sz[100];

void init(int n){
    for(int i = 0; i < n; i++){
        p[i] = i;
        sz[i] = 1;
    }
}

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    if (x != y){
        p[x] = y;
        sz[y] += sz[x];
    }
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    n *= 3;
    fact[0] = 1;
    for(int i = 1; i < maxn; i++) fact[i] = mul(fact[i - 1], i);
    invfact[maxn - 1] = qpow(fact[maxn - 1], mod - 2);
    for(int i = maxn - 2; i >= 0; i--){
        invfact[i] = mul(invfact[i + 1], i + 1);
    }
    powfact3[0] = 1;
    for(int i = 1; i < maxn; i++){
        powfact3[i] = mul(powfact3[i - 1], invfact[3]);
    }

    auto C = [&](int a, int b){
        if (a < 0 or b < 0 or a < b) return 0;
        return mul(mul(fact[a], invfact[b]), invfact[a - b]);
    };

    vector<pair<int, int> > v[2];
    vector<int> q;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        q.push_back(a);
        q.push_back(b);
        v[c].push_back({a, b});
    }

    sort(q.begin(), q.end());
    q.erase(unique(q.begin(), q.end()), q.end());
    vector<int> id(n + 1);
    for(int i = 0; i < q.size(); i++){
        id[q[i]] = i;
    }

    int ans = 0;
    const int s = v[1].size();
    for(int i = 0; i < 1 << s; i++){
        init(q.size());
        for(auto [x, y] : v[0]){
            merge(id[x], id[y]);
        }
        for(int j = 0; j < s; j++){
            if (i >> j & 1){
                auto [x, y] = v[1][j];
                merge(id[x], id[y]);
            }
        }
        bool ok = true;
        int cnt[4]{};
        cnt[1] = n - q.size();
        for(int i = 0; i < q.size(); i++){
            if (find(i) == i){
                if (sz[i] > 3){
                    ok = false;
                    break;
                }
                cnt[sz[i]] += 1;
            }
        }
        if (!ok or cnt[2] > cnt[1]) continue;
        int sum = mul(C(cnt[1], cnt[2]), fact[cnt[2]]);
        cnt[1] -= cnt[2];
        int t = mul(fact[cnt[1]], powfact3[cnt[1] / 3]);
        t = mul(t, invfact[cnt[1] / 3]);
        if (__builtin_parity(i)) sub(ans, mul(sum, t));
        else add(ans, mul(sum, t));
    }
    cout << ans << '\n';

}