#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define si(v) int(v.size())
#define len(v) int(v.length())
#define lob(v,n) lower_bound(all(v),n)
#define lobi(v,n) lower_bound(all(v),n) - v.begin()
#define upb(v,n) upper_bound(all(v),n)
#define upbi(v,n) upper_bound(all(v),n) - v.begin()
#define mod 1000000007
#define infi 1010000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M;
    cin >> N >> M;
    
    vvl dp(N+1,vl(int(1<<N),0));
    dp[0][0] = 1;
    
    ve<ve<pii>> A(N+1);
    rep(i,M) {
        int x;
        cin >> x;
        int y,z;
        cin >> y >> z;
        A[x].pb(make_pair(y,z));
    }
    
    
    rep(i,N) rep(j,int(1<<N)) if(dp[i][j] > 0){
        rep(k,N) if(!(j & 1 << k)) {
            int b = int(j | 1 << k);
            int f = 1;
            for (pii a : A[i+1]) {
                int n = 0;
                rep(ii, a.fi) if(b & 1 << ii) n++;
                if(n > a.se){
                    f = 0;
                    break;
                }
            }
            if(f){
                dp[i+1][b] += dp[i][j];
            }
                
                
        }
        
    }
    //outmat(dp);

    cout << dp[N][int(1<<N)-1] << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_set>
#include <random>
#include <algorithm>
#define INF (1ll<<60)
#define ll long long
using namespace std;

vector<pair<int,int>> counts[22];

bool HasBit(int x, int b) {
    return ((x>>b)&1);
}

ll dp[(1<<18)+1];

ll Solve(int N, int mask, int x) {

    if (x == N) {
        return 1;
    }

    if (dp[mask]!=-1) return dp[mask];
    ll ans=0;
    for(int val=0;val<N;val++) {
        if (HasBit(mask,val)) continue;
        int nmask = (mask|(1<<val));
        bool ok=true;
        for(pair<int,int> yz : counts[x]) {
            int y = yz.first;
            int z = yz.second;
            if (__builtin_popcount(nmask&((1<<(y+1))-1)) > z) ok=false;
        }
        if (ok) {
            ans += Solve(N, nmask, x+1);
        }
    }
    dp[mask]=ans;
    return ans;
}

int main() {
    int N,M;
    cin>>N>>M;
    for(int i=1;i<=M;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        x--;
        y--;
        counts[x].push_back({y,z});
    }
    for(int mask=0;mask<(1<<N);mask++)
        dp[mask]=-1;
    cout << Solve(N, 0, 0) << endl;
}