Example

Input

2 2
1 2 0
3 4 1


Output

2
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2)  return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
const int N=3000005;

struct modi{  
  int x,y,r;  
}Stk[N]; int pnt;  
int fat[N],rnk[N],size[N];  
  
inline int Fat(int u){  
  return u==fat[u]?u:Fat(fat[u]);  
}

int cot[N];
int flag=0;

inline int Merge(int x,int y){  
  x=Fat(x); y=Fat(y); if (x==y) return 0;  
  if (rnk[x]>rnk[y]) swap(x,y);  
  Stk[++pnt].x=x; Stk[pnt].y=y; Stk[pnt].r=0;  
  if (rnk[x]==rnk[y]) rnk[y]++,Stk[pnt].r=1;  
  fat[x]=y; cot[size[y]]--; cot[size[x]]--; size[y]+=size[x]; cot[size[y]]++;
  if (size[y]>3) flag=1;
  return 1;  
}

inline void Back(int t){  
  for (;pnt>t;pnt--){
    int x=Stk[pnt].x,y=Stk[pnt].y;
    fat[Stk[pnt].x]=Stk[pnt].x;  
    if (Stk[pnt].r) rnk[Stk[pnt].y]--;
    cot[size[y]]--; size[y]-=size[x]; 
    cot[size[y]]++; cot[size[x]]++; 
  }  
}

const ll P=1e9+9;

ll fac[N],inv[N],iinv[N];

int tot;
int us[20],vs[20],ws[20];
int n,m;

inline ll Pow(ll a,int b){
  ll ret=1;
  for (;b;b>>=1,a=a*a%P)
    if (b&1)
      ret=ret*a%P;
  return ret;
}

inline void Pre(int n){  
  fac[0]=1; for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%P;
  inv[0]=1; for (int i=1;i<=n/3;i++) (inv[i]=inv[i-1]*6)%=P;
  for (int i=1;i<=n/3;i++) inv[i]=Pow(inv[i],P-2);
  iinv[1]=1; for (int i=2;i<=n;i++) iinv[i]=(P-P/i)*iinv[P%i]%P;  
  iinv[0]=1; for (int i=1;i<=n;i++) iinv[i]=iinv[i]*iinv[i-1]%P;  
}

inline ll Calc(int a,int b,int c){
  if (b>a) return 0;
  return fac[a]*inv[(a-b)/3]%P*iinv[(a-b)/3]%P;
}

int main(){
  read(n); read(m); n*=3;
  Pre(n);
  tot=0;
  for (int i=1;i<=n;i++) fat[i]=i,size[i]=1;
  flag=0; cot[1]=n;
  for (int i=1;i<=m;i++){
    ++tot;
    read(us[tot]),read(vs[tot]),read(ws[tot]);
    if (ws[tot]==0)
      Merge(us[tot],vs[tot]),tot--;      
  }
  if (flag){
    printf("0\n");
    return 0;
  }
  ll Ans=Calc(cot[1],cot[2],cot[3]);
  int tmp=pnt;
  for (int i=1;i<(1<<tot);i++){
    flag=0; int c=0;
    for (int j=1;j<=tot;j++)
      if (i>>(j-1)&1)
	Merge(us[j],vs[j]),c++;   
    if (!flag){
      if (c&1)
	(Ans+=P-Calc(cot[1],cot[2],cot[3]))%=P;
      else
	(Ans+=Calc(cot[1],cot[2],cot[3]))%=P;
    }
    Back(tmp);
  }
  printf("%lld\n",Ans);
  return 0;
}