#include <bits/stdc++.h>
using namespace std;

#define Gene template< class
#define Rics printer& operator,
Gene c> struct rge{c b, e;};
Gene c> rge<c> range(c i, c j){ return {i, j};}
struct printer{
    ~printer(){cerr<<endl;}
    Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
    Rics(string x){cerr<<x;return *this;}
    Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
    Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
    Gene c >Rics(rge<c> x){
        *this,"["; for(auto it = x.b; it != x.e; ++it)
            *this,(it==x.b?"":", "),*it; return *this,"]";}
};
#define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
#define dbg(x) "[",#x,": ",(x),"] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r) {
    return uniform_int_distribution<int>(l, r) (rng);
}

int P(int u, vector<int> &par) {
    return par[u] = (par[u]^u ? P(par[u], par) : u);
}

const int N = 3e6 + 100;
int mod = 1e9 + 9;

namespace Combi {
    int fact[N], inv[N];

    int bm(int b, int p, int m) {
        if(p == 0) return 1%m;
        int t = bm(b,p/2,m);
        t = (1ll*t*t)%m;
        if(p&1) return 1ll*t*b%m;
        return t;
    }

    int C(int n, int r) {
        if(n < 0 or r < 0 or r > n) return 0;
        int ret = 1ll*fact[n]*inv[r]%mod;
        ret = 1ll*ret*inv[n-r]%mod;
        return ret;
    }
    // X1 + X2 + ... + Xvar = Sum
    int no_of_eqns(int var, int sum) {
        return C(sum+var-1,var-1); // Xi >= 0
        // return C(sum-1,var-1); // Xi > 0
    }
    /// divide a set of n size into k non-empty sets O(klogn)
    int stirling(int n, int k)  {
        int ans = 0;
        for(int i = 0; i <= k; i++) {
            int x = 1ll*C(k,i)*bm(k-i,n,mod)%mod;
            if(i&1) ans -= x;
            else ans += x;
            ans %= mod;
            ans += mod;
            ans %= mod;
        }
        ans = 1ll*ans*inv[k]%mod;
        return ans;
    }

    void init() {
        fact[0] = 1;
        for(int i = 1; i < N; i++) {
            fact[i] = 1ll*fact[i-1]*i%mod;
        }
        inv[N-1] = bm(fact[N-1], mod-2, mod);
        for(int i = N-2; i >= 0; i--) {
            inv[i] = 1ll*inv[i+1]*(i+1)%mod;
        }
    }
}



int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    Combi::init();

    int n, m;
    cin >> n >> m;
    map<int,int> ids;
    int id = 0;
    vector<pair<int,int>> edges[2];
    for(int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        if(ids.find(u) == ids.end()) ids[u] = id++;
        if(ids.find(v) == ids.end()) ids[v] = id++;
        edges[c].push_back({ids[u], ids[v]});
    }
    int X = edges[1].size();
    int inv6 = Combi::bm(6, mod-2, mod);
    int result = 0;
    for(int mask = 0; mask < (1<<X); mask++) {
        vector<int> par(id), sz(id, 1);
        for(int i = 0; i < id; i++) par[i] = i;
        for(int i = 0; i < edges[0].size(); i++) {
            int u = edges[0][i].first, v = edges[0][i].second;
            u = P(u, par), v = P(v, par);
            if(u == v) continue;
            if(sz[v] > sz[u]) swap(u, v);
            par[v] = u;
            sz[u] += sz[v];
        }
        for(int i = 0; i < X; i++) {
            if(!((mask >> i) & 1)) continue;
            int u = edges[1][i].first, v = edges[1][i].second;
            u = P(u, par), v = P(v, par);
            if(u == v) continue;
            if(sz[v] > sz[u]) swap(u, v);
            par[v] = u;
            sz[u] += sz[v];
        }
        bool ok = true;
        int two = 0, one = 3*n-id;
        for(int i = 0; i < id; i++) {
            if(par[i] != i) continue;
            if(sz[i] > 3) {
                ok = false;
                break;
            }
            if(sz[i] == 2) two++;
            if(sz[i] == 1) one++;
        }
        if(ok == false or two > one) continue;
        int ways = 1ll*Combi::C(one, two)*Combi::fact[two]%mod;
        ways = 1ll*ways*Combi::fact[one-two]%mod;
        int inv = Combi::bm(inv6, (one-two)/3, mod);
        ways = 1ll*ways*inv%mod;
        ways = 1ll*ways*Combi::inv[(one-two)/3]%mod;
        if(__builtin_popcount(mask) & 1) result -= ways;
        else result += ways;

        result %= mod;
    }

    if(result < 0) result += mod;
    cout << result << endl;
}