#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
typedef pair<int,int> pir;
string sstr[]={"NO\n","YES\n"};
const int N=30;
class node
{
public:
	int lay;
	int st;
};
int T,n,m;
int g[N][N];
int p3[N];
queue<node> q;
int ans=0;
//
bool check(int a,int b,int c)
{
	if(a==b&&b==c) return 1;
	if(a!=b&&b!=c&&a!=c) return 1;
	return 0;
}
signed main()
{
	p3[0]=1;
	for(int i=1;i<=20;i++) p3[i]=p3[i-1]*3;
	cin>>n>>m;
	memset(g,-1,sizeof(g));
	for(int i=1;i<=m;i++){
		int x,y,c;
		cin>>x>>y>>c;
		g[x][y-1]=c;
	}
	if(g[1][0]==-1){
		q.push(node{1,0});
		q.push(node{1,1});
		q.push(node{1,2});
	}
	else q.push(node{1,g[1][0]});
	while(!q.empty()){
		auto tmp=q.front();
		int lay=tmp.lay;
		//cout<<"|||"<<lay<<' '<<tmp.st<<'\n';
		q.pop();
		if(tmp.lay==n){
			ans++;
			continue;
		}
		for(int i=0;i<3;i++){//枚举第一个
			if(g[lay+1][0]!=-1&&g[lay+1][0]!=i) continue;
			int cur=i;//当前数值
			int pre=i;
			int cst=i;//当前状态
			bool flag=1;
			//cout<<"---"<<i<<'\n';
			for(int j=1;j<=lay;j++){
				int up=tmp.st/p3[j-1]%3;
				if(up==pre) cur=pre;
				else if(up!=0&&pre!=0) cur=0;
				else if(up!=1&&pre!=1) cur=1;
				else cur=2;
				//cout<<"+++"<<i<<' '<<j<<' '<<cur<<' '<<'\n';
				if(g[lay+1][j]!=-1&&g[lay+1][j]!=cur){
					flag=0;
					break;
				}
				//cout<<"***"<<lay<<' '<<tmp.st<<' '<<i<<' '<<j<<' '<<cur<<'\n';
				pre=cur;
				cst+=cur*p3[j];
			}
			if(flag) q.push(node{lay+1,cst});
		}

	}
	cout<<ans<<'\n';

}