#include<bits/stdc++.h>
using namespace std;
using P = pair<int64_t,int64_t>;
const int MAX = (1<<19);
int64_t dp[MAX];
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<P>> vec(N,vector<P>(0));
  for(int i=0; i<M; i++){
    int X, Y, Z;
    cin >> X >> Y >> Z;
    X--;
    vec[X].push_back(P(Y,Z));
  }
  dp[0] = 1;
  for(int i=0; i<(1<<N); i++){
    int c = 0;
    vector<int> sum(N);
    for(int j=0; j<N; j++){
      if(i & (1<<j)){
        c++;
        sum[j]++;
      }
      if(j != 0){
        sum[j] += sum[j-1];
      }
    }
    //何を追加するか？
    for(int j=0; j<N; j++){
      if(i & (1<<j)){
        continue;
      }
      bool flag = true;
      for(int k=0; k<vec[c].size(); k++){
        auto[y,z] = vec[c][k];
        if(j < y){
          z--;
        }
        if(sum[y-1] > z){
          flag = false;
          break;
        }
      }
      if(flag){
        dp[i|(1<<j)] += dp[i];
      }
    }
  }
  cout << dp[(1<<N)-1] << endl;        
}
  
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<(a)<<endl
#define dumparr(a,n) cerr<<#a<<"["<<(n)<<"]="<<(a[n])<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

pll operator+(pll a,pll b){
  return pll(a.first+b.first,a.second+b.second);
}
pll operator-(pll a,pll b){
  return pll(a.first-b.first,a.second-b.second);
}
pll operator*(ll a,pll b){
  return pll(b.first*a,b.second*a);
}
const ll INF=(1LL<<60);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  a=abs(a);
  b=abs(b);
  if(a==0)return b;
  if(b==0)return a;
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


int main(){
  cout<<setprecision(1000);
  ll N,M;
  cin>>N>>M;
  vector<ll> dp(1LL<<N);
  vector<vector<pll>> cond(N);
  REP(M){
    ll x,y,z;
    cin>>x>>y>>z;
    --x;--y;
    cond[x].push_back(pll(y,z));
  }
  auto f=[](ll num,ll y,ll z){
    ll mask=(1LL<<(y+1))-1;
    num&=mask;
    return __builtin_popcountll(num)<=z;
  };
  dp[0]=1;
  For(j,(1LL<<N)){
    ll n=__builtin_popcountll(j);
    if(n==N)continue;
    ll cur=1;
    REP(N){
      if((cur&j)==0){
        ll jj=(j|cur);
        ([&]() {
          FOR(cidx, n, N)
          {
            for (auto &&[y, z] : cond[cidx])
            {
              if (!f(jj, y, z))
              {
                return;
              }
            }
          }
          dp[jj]+=dp[j];
        })();
      }
      cur<<=1;
    }
  }
  dump(dp);
  cout<<dp[(1LL<<N)-1]<<endl;
  return 0;
}
