#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;
ll MOD = 1e9+9;
template<typename T> 
constexpr T modpow(T a,T n,T mod=MOD){//(a^n)%MOD
    T ret=1;
    while(n>0){
        if((n&1)!=0){//n%2==1
            ret=ret*a%mod;
        }
        a=a*a%mod;
        n=n/2;
    }
    return ret;
}
std::vector<long long> fac;
std::vector<long long> ifac;

template <typename T>
T modcomb(T a, T b){
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    long long tmp = ifac[a-b]* ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}


void combinit(int maxn){
    fac.resize(maxn+1);
    ifac.resize(maxn+1);
    fac[0] = 1;
    ifac[0] = 1;
    for(long long i = 0; i<maxn; i++){
        fac[i+1] = fac[i]*(i+1) % MOD;
        ifac[i+1] = ifac[i]*modpow(i+1, MOD-2) % MOD;
    }
}

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }

};

int main(){
    ll n , m;
    cin>>n>>m;
    combinit( 3*n );
    //cout<<"OK"<<endl;
    vector<mp> good,bad;
    set<int> use;
    for(int i=0;i<m;i++){
	int a,b,c;
	cin>>a>>b>>c;
	use.insert( a );
	use.insert( b );
	if( c == 0 ){
	    good.push_back( mp( a , b ) );
	}else{
	    bad.push_back( mp( a , b ) );
	}
    }
    //cout<<good.size()<<bad.size()<<endl;
    map<ll,int> change;
    int j=0;
    for(auto i:use){
	change[i] = j++;
    }
    //cout<<"OK"<<endl;
    UnionFind uni( j+1 );
    for(int i=0;i<good.size();i++){
	uni.unite( change[ good[i].first] , change[ good[i].second ] );
    }
    //ll nkai = 1;
    //for(int i=2;i<=n;i++) {
	//nkai *= i;
	//nkai %= MOD;
    //}
    //nkai = modpow( nkai , MOD-2 );
    //for(auto i:use)cout<<i<<' '<<change[i]<<' '<<uni.size( change[i] )<<endl;
    vector<ll> dp( (1<<bad.size() ) , 1 );
    for(int i=0;i< ( 1<< bad.size() );i++){
	UnionFind tmp = uni;
	for(int j=0;j<bad.size();j++){
	    if( (i>>j)&1 ){
		//cout<<"LOCK"<<bad[j].first<<' '<<bad[j].second;
		tmp.unite( change[bad[j].first] , change[bad[j].second] );
	    }
	}
	ll rest = 3*n;
	//cout<<rest<<endl;
	int cnt2 = 0;
	bool flag = false;
	//cout<<"SIZE"<<use.size()<<endl;
	for(auto j:use){
	    if( tmp.find( change[j] ) == change[j] ){
		int sz = tmp.size( change[j] );
		//cout<<"UNION"<<j<<' '<<change[j]<<' '<<sz<<endl;
		if( sz == 2 ){
		    //cout<<"LL"<<endl;
		    rest-=2;
		    cnt2++;
		}
		if( sz == 3 ){
		    rest-=3;
		    //cout<<"OK"<<endl;
		}
		if( sz > 3 ){
		    dp[i] = 0;
		    flag = true;
		    break;
		}
	    }
	}
	if( flag ) continue;
	dp[i] = 1;
	for(int j=0;j<cnt2;j++){
	    dp[i]*= rest;
	    dp[i]%= MOD;
	    rest--;
	}
	if( rest%3 != 0 ){
	    cout<<"Maybe"<<endl;
	    return 0;
	}
	ll nn = rest/3;
	ll nkai = ifac[nn];
	dp[i]*=nkai;
	dp[i]%=MOD;
	/*while(rest > 0 ){
	    //dp[i]*=modcomb( rest , 3ll );
	    dp[i] *=  (rest*(rest-1)*(rest-2)/6)%MOD;
	    dp[i]%=MOD;
	   // cout<<"REST"<<rest<<' '<<dp[i]<<endl;
	    rest-=3;
	}*/
	dp[i]*=fac[rest];
	dp[i]%=MOD;
	ll six = modpow( 6LL ,  nn );
	six = modpow( six , MOD-2 );
	dp[i]*=six;
	dp[i]%=MOD;
	//cout<<i<<' '<<dp[i]<<endl;
    }
    ll res = 0;
    for(int i=0;i<(1<<bad.size() );i++){
	int cnt = 0;
	for(int j=0;j<bad.size();j++)if( (i>>j)&1 )cnt++;
	if( cnt%2 == 0 ){
	    res += dp[i];
	    res %= MOD;
	}else{
	    res +=( MOD-dp[i] );
	    res %= MOD;
	}
    }
    //if( bad.size()%2 == 1 )cout<<(MOD-res)%MOD<<endl;
     cout<<res<<endl;
    return 0;
}



Measured memory_bytes: 51544