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

#define ff first
#define ss second
#define PI acos(-1)
#define pb push_back
#define int long long
#define ld long double
#define sp fixed<<setprecision
#define bp __builtin_popcountll
#define all(x) x.begin(),x.end()
#define pii pair<long long,long long>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const int M = (1e9)+7;
const int N = 505;
const int INF = 1e12;

int n,m;
int x[105], y[105], z[105];
int memo[(1<<19)][20];

int solve(int mask, int pos)
{
    // cout<<mask<<" "<<pos<<endl;
    if(pos == n)return 1;
    if(memo[mask][pos] != -1) return memo[mask][pos];
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        if(!((mask>>i)&1LL))
        {
            int ok = 1;
            int new_mask = mask|(1LL<<i);
            for(int j=0;j<m;j++)
            {
                if(x[j]>=pos)
                {
                    int cnt = 0;
                    for(int k=0;k<=y[j];k++) cnt += ((new_mask>>k)&1LL);
                    ok &= (cnt <= z[j]);
                }
            }
            // cout<<new_mask<<endl;
            if(ok) ans += solve(new_mask, pos+1);
        }
    }
    // cout<<mask<<" "<<pos<<" "<<ans<<endl;
    memo[mask][pos] = ans;
    return ans;
}


signed main()
{
  FAST
  int tc=1;
//   cin>>tc;
  for(int ti=1;ti<=tc;ti++)
  {
      cin>>n>>m;
      for(int i=0;i<m;i++) cin>>x[i]>>y[i]>>z[i], x[i]--,y[i]--;
      for(int i=0;i<(1LL<<n);i++)for(int j=0;j<n;j++)memo[i][j] = -1;
      int ans = solve(0, 0);
      cout<<ans<<endl;
  }
  return 0;
}
#include<cstdio>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
using namespace std;
const int N=20,M=105;
template<typename T>void read(T &x)
{
	bool neg=false;
	unsigned char c=getchar();
	for(;(c^48)>9;c=getchar())if(c=='-')neg=true;
	for(x=0;(c^48)<10;c=getchar())x=(x<<3)+(x<<1)+(c^48);
	if(neg)x=-x;
}
int n,m,x[M],y[M],z[M],pop[1<<N],bit[1<<N][N];
long long f[1<<N];
bool check(int i,int j)
{
	F(k,0,m)if(i==x[k]&&bit[j][y[k]]>z[k])return false;
	return true;
}
int main()
{
	read(n);read(m);
	F(i,0,m)read(x[i]),read(y[i]),read(z[i]);
	F(i,1,1<<n)pop[i]=pop[i^(i&-i)]+1;
	F(i,0,1<<n)F(j,0,n)bit[i][j+1]=bit[i][j]+(i>>j&1);
	f[0]=1;
	F(i,0,n)F(j,0,1<<n)if(pop[j]==i)
	{
		if(i==0||check(i,j))
			F(k,0,n)if((j>>k&1)==0)
			{
				int v=j^1<<k;
				f[v]+=f[j];
			}
	}
	printf("%lld\n",f[(1<<n)-1]);
	return 0;
}
