#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n, m;
vector<int> y[18], z[18];
int dp[19][1 << 18];
int bitCnt[1 << 18];

signed main() {
	int i, j, k;
	
	cin >> n >> m;
	
	rep(i, (1 << n)) {
		rep(j, n) {
			if ((i >> j) % 2) bitCnt[i]++;
		}
	}
	
	rep(i, m) {
		int x, cy, cz;
		cin >> x >> cy >> cz;
		y[x].push_back(cy);
		z[x].push_back(cz);
	}
	
	dp[0][0] = 1;
	rep(i, n) {
		rep(j, (1 << n)) {
			if (dp[i][j] == 0) continue;
			
			//判定
			rep(k, y[i].size()) {
				int bcnt = bitCnt[j & ((1 << y[i][k]) - 1)];
				if (bcnt > z[i][k]) break;
			}
			if (k < y[i].size()) continue;
			
			//遷移
			rep(k, n) {
				if ((j >> k) % 2) continue;
				dp[i + 1][j + (1 << k)] += dp[i][j];
			}
		}
	}
	
	cout << dp[n][(1 << n) - 1] << endl;
	return 0;
}
//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 18;
const int MAXM = 105;
int n,m;
LL dp[1 << MAXN],pre[MAXN];

LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

struct node
{
    int x,y,z;
    bool operator < (const node &px)const{
        return x < px.x;
    }
}s[MAXM];

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    n = Read(); m = Read();
    int S = (1 << n) - 1;
    for(int i = 0;i < m;++ i) s[i].x = Read(),s[i].y = Read(),s[i].z = Read();
    for(int i = 1;i <= S;++ i)
    {
        int cnt = 0,dz = i;
        while(dz)
        {
            if(dz & 1) cnt++;
            dz >>= 1;
        }
        for(int j = 0;j < n;++ j) pre[j] = 0;
        for(int j = 0;j < n;++ j)
            if((i >> j) & 1) pre[j]++;
        for(int j = 1;j < n;++ j) pre[j] += pre[j-1];
        for(int j = 0;j < m;++ j)
        {
            if(s[j].x == cnt && pre[s[j].y-1] > s[j].z)
            {
                dp[i] = -1;
                break;
            }
        }
    }
    dp[0] = 1;
    for(int i = 1;i <= S;++ i)
    {
        if(dp[i] == -1) continue;
        for(int j = 0;j < n;++ j)
            if((i >> j) & 1)
                if(dp[i^(1<<j)] != -1)
                    dp[i] += dp[i^(1<<j)];
    }
    Put(Max(dp[S],0ll));
	return 0;
}
