#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
const int MAXM = 22;
ll fac[3*MAXN], mypow[3*MAXN];
int a[MAXM], b[MAXM], c[MAXM], fa[MAXM*2], sum[MAXM*2];
bool vis[MAXM];
const int MOD = 1e9+9;
vector<int> q;
map<int, int> Map;
int ans;
int n, m;
int A(int n, int m){
    ll ret = 1;
    for(int i = 1; i <= m; i++) ret = ret * (n--) % MOD;
    return ret;
}
int expMod(int e, int n, int p){
    int ret = 1;
    for(; n; n >>= 1, e = (ll)e*e%MOD)
        if(n&1)
            ret = (ll) ret * e % MOD;
    return ret;
}
int ni(int n){
    return expMod(n, MOD - 2, MOD);
}

int B(int n){
    n /= 3;
    return ((ll)fac[3 * n] * ni(fac[n])%MOD) * ni(mypow[n]) % MOD;
}

int getfa(int i){
    if(fa[i] == i) return i;
    else return fa[i] = getfa(fa[i]);
}

void add(int i, int j){
    i = Map[i];
    j = Map[j];
    int p = getfa(i), q = getfa(j);
    if(p != q){
        fa[q] = p;
        sum[p] += sum[q];
    }
}

int calc(int p){
    for(int i = 0; i < q.size(); i++) fa[i] = i, sum[i] = 1;
    for(int i = 1; i <= m; i++) if(c[i] == 0 || vis[i]) add(a[i], b[i]);
    int cnt = 0, cnt3 = 0;
    for(int i = 0; i < q.size(); i++) if(fa[i] == i) {
        if(sum[i] > 3) return 0;
        if(sum[i] == 3) cnt3++;
        if(sum[i] == 2) cnt++;
    }
    int left = 3 * n - cnt * 2 - cnt3 * 3;
    if(left < cnt) return 0;
    return (long long) A(left, cnt) * B(left - cnt) * p % MOD;
}

void dfs(int v, int p){
    if(v == m+1) return;
    if(c[v] == 0) {
        dfs(v+1, p);
        return;
    }
    vis[v] = true;
    ans = (ans + calc(-p)) % MOD;
    dfs(v+1, -p);
    vis[v] = false;
    dfs(v+1, p);
}
int main(){
    fac[0] = 1;
    mypow[0] = 1;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= 3 * n; i++) fac[i] = fac[i-1] * i % MOD;
    for(int i = 1; i <= n; i++) mypow[i] = mypow[i-1] * 6 % MOD;
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);
    for(int i = 1; i <= m; i++) q.push_back(a[i]), q.push_back(b[i]);
    sort(q.begin(), q.end());
    q.erase(unique(q.begin(), q.end()), q.end());
    for(int i = 0; i < q.size(); i++)  Map[q[i]] = i;
    memset(vis, 0, sizeof(vis));
    ans = calc(1);
    dfs(1, 1);
    printf("%d\n", (ans+MOD)%MOD);
    return 0;
}