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

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; }

#define SPC << " " <<
#define DEBUG(x) cerr << #x << " = "; cerr << x << endl;
#define DEBUG_ITER(x) cerr << #x << " = "; for (auto _ : x) cerr << _ << ' '; cerr << endl;

typedef pair<int,int> PII;
typedef long long int64;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<double> VD;

int n,m;
vector<PII> v[20];


int64 f[20][1<<20];
int64 solve(int i, int m) {
    if (i==n) return 1;
    if (f[i][m]!=-1) return f[i][m];
    int64 r=0;
    REP (j,n) if ((m&(1<<j))==0) {
        int mm=m|(1<<j), ok=1;
        for (auto [y,z] : v[i]) {
            int k=__builtin_popcount(mm&((1<<y)-1));
            if (k>z) ok=0;
        }
        if (ok) r+=solve(i+1, mm);
    }
    f[i][m]=r;
    return r;
}

int main() {
    //freopen("test.in","r",stdin);
    cin >> n >> m;
    REP (i,m) {
        int x,y,z;
        cin >> x >> y >> z;
        x--;
        v[x].PB({y,z});
    }
    INIT(f,-1);
    cout << solve(0,0) << endl;
    return 0;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>
// #include "atcoder/all"

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}




signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> x(m), y(m), z(m);
    vector<vector<pair<int,int>>> c(n);
    for(int i = 0; i < m; ++i){
        cin >> x[i] >> y[i] >> z[i];
        c[x[i]].emplace_back(y[i] - 1, z[i]);
    }

    vector<vector<i64>> dp(n + 1, vector<i64>(1 << n, 0));
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < (1 << n); ++j){

            vector<int> r(n + 1, 0);
            for(int k = 0; k < n; ++k){
                if(j & (1 << k))
                    ++r[k];
            }
            for(int k = 0; k < n; ++k){
                r[k + 1] += r[k];
            }
            for(auto [pre, cnt] : c[i]){
                if(r[pre] > cnt){
                    dp[i][j] = 0;
                    break;
                }
            }
            if(dp[i][j] == 0)
                continue;

            for(int k = 0; k < n; ++k){
                if(j & (1 << k))
                    continue;
                dp[i + 1][j | (1 << k)] += dp[i][j];
            }
        }
    }
    cout << dp.back().back() << endl;

    return 0;
}
