Example

Input

2 2
1 2 0
3 4 1


Output

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000009

struct UnionFind{
  vector<int> v,sav;
  UnionFind(int n) : v(n, -1) {}
  void init(){
    for(int i = 0;i < (int)sav.size();i++)v[sav[i]]=-1;
    sav.clear();
  }
  int find(int x) { return v[x] < 0 ? x : find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    sav.push_back(x); sav.push_back(y);
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};

ll mod_pow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll N,M;
vector<P> rel[2];
ll fac[3000010],finv[3000010];
ll calc[3000010];

ll comb(ll n,ll r){
  if(n<0||r<0||n<r)return 0;
  return (fac[n]*finv[r]%mod)*finv[n-r]%mod;
}

int main(){
  fac[0]=1;
  rep(i,3000000)fac[i+1]=fac[i]*(i+1)%mod;
  rep(i,3000001)finv[i]=mod_pow(fac[i],mod-2);
  calc[0]=1;
  for(ll i=3;i<=3000000;i+=3){
    calc[i]=calc[i-3]*comb(i,3)%mod;
    (calc[i]*=mod_pow(i/3,mod-2))%=mod;
  }

  cin>>N>>M;
  N*=3;
  rep(i,M){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    rel[c].push_back(P(a,b));
  }
  ll res=0;
  M=rel[1].size();
  UnionFind uf(N);
  rep(S,1<<M){
    uf.init();
    set<ll> vs;
    rep(i,rel[0].size()){
      uf.unite(rel[0][i].fi,rel[0][i].se);
      vs.insert(rel[0][i].fi); vs.insert(rel[0][i].se);
    }
    rep(i,M){
      if((S>>i)&1){
        uf.unite(rel[1][i].fi,rel[1][i].se);
        vs.insert(rel[1][i].fi); vs.insert(rel[1][i].se);
      }
    }
    ll crt=1;
    ll rest=N,cnt=0;
    map<ll,bool> used;
    for(ll v : vs){
      if(!used[uf.find(v)]){
        used[uf.find(v)]=true;
        ll sz=uf.size(v);
        if(sz>3)crt=0;
        else{
          rest-=sz;
          cnt+=3-sz;
        }
      }
    }
    (crt*=(comb(rest,cnt)*fac[cnt])%mod)%=mod;
    rest-=cnt;

    if(bcnt(S)%2==0) (res+=calc[rest]*crt%mod)%=mod;
    else (res+=(mod-(calc[rest]*crt%mod))%mod)%=mod;
  }
  cout<<res<<endl;
  return 0;
}

