#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;

#define MAX_N 3000001

typedef long long int64;

const int64 mod = 1e9 + 9;

inline int64 extgcd(int64 a, int64 b, int64 &x, int64 &y) {
  int64 d = a;
  if(b != 0) d = extgcd(b, a % b, y, x), y -= (a / b) * x;
  else x = 1, y = 0;
  return d;
}

inline int64 modPow(int64 x, int64 n) {
  if(n == 0) return 1;
  int64 ret = modPow(x, n/2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return ret;
}

inline int64 modInv(int64 a) {
  return modPow(a, mod - 2);
}

inline int64 modFact(int n) {
  int64 ret = 1;
  while(n > 1) (ret *= n--) %= mod;
  return ret;
}

int64 fact[MAX_N], invfact[MAX_N];
void init() {
  fact[0] = invfact[0] = 1;
  for(int i = 1; i < MAX_N; i++) {
    fact[i] = fact[i-1] * i % mod;
    invfact[i] = modInv(fact[i]);
  }
}

inline int64 modComb(int64 n, int64 r) {
  if(r < 0 || n < r) return 0;
  return fact[n] * invfact[r] % mod * invfact[n-r] % mod;
}

struct UnionFind
{
  vector<int> data;
  UnionFind(){}
  UnionFind(int sz):data(sz, -1){};
  int size(int x) { return -data[find(x)]; }
  int find(int x) {
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y]; data[y] = x;
    return;
  }
};

int pow6[MAX_N];
int invpow6[MAX_N];
int calc(int& n, vector<Tapris>& vec) {
  //UnionFind uf(n);
  //set<int> st;
  vint press;
  rep(i, vec.size()) {
    int a, b, c;
    tie(a, b, c) = vec[i];
    if(c == 1) continue;
    //uf.unite(a, b);
    //st.insert(a);
    //st.insert(b);
    press.push_back(a);
    press.push_back(b);
  }
  sort(all(press));
  press.erase(unique(all(press)), press.end());
  UnionFind uf(press.size());
  rep(i, vec.size()) {
    int a, b, c;
    tie(a, b, c) = vec[i];
    if(c == 1) continue;
    a = lower_bound(all(press), a)-press.begin();
    b = lower_bound(all(press), b)-press.begin();
    uf.unite(a, b);
  }
  int x = 0, y = 0;
  //for(int a : st) {
  rep(i, press.size()) {
    if(uf.find(i) == i) {
      int sz = uf.size(i);
      if(sz >= 4) return 0;
      else if(sz == 2) ++y;
    }
  }
  x = n - press.size();
  if(y > x) return 0;
  int z = (x-y)/3;
  return fact[x]*invpow6[z]%mod*invfact[z]%mod;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  init();
  pow6[0] = invpow6[0] = 1;
  reps(i, 1, MAX_N) {
    pow6[i] = pow6[i-1]*6 % mod;
    invpow6[i] = modInv(pow6[i]);
  }

  int n, m;
  cin >> n >> m;
  n *= 3;
  vector<Tapris> vec;
  vector<int> badidx;
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c; --a, --b;
    vec.emplace_back(a, b, c);
    if(c == 1) badidx.push_back(i);
  }
  //cout<<calc(n, vec)<<endl;
  int bad = badidx.size();
  int ans = 0;
  rep(bit, 1<<bad) {
    rep(i, bad) if((bit>>i)&1) get<2>(vec[badidx[i]]) = 0;
    if(__builtin_popcount(bit)%2) ans = (ans-calc(n, vec)+mod) % mod;
    else ans = (ans+calc(n, vec)) % mod;
    rep(i, bad) if((bit>>i)&1) get<2>(vec[badidx[i]]) = 1;
  }
  cout << ans%mod << endl;

  return 0;
}

Measured memory_bytes: 96980