#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/












vector<ll> masks;
#define pcnt __builtin_popcount
int N, M;
ll dp[1 << 18];
vector<pair<int, int>> restrictions[18];
//---------------------------------------------------------------------------------------------------
int tot[19];
bool check(int msk) {




	int cnt = 0;
	rep(i, 1, N + 1) tot[i] = 0;
	rep(i, 0, N) if (msk & (1 << i)) {
		tot[i + 1]++;
		cnt++;
	}
	rep(i, 2, N + 1) tot[i] += tot[i - 1];
	
//	fore(p, restrictions[cnt]){
	fore(p, restrictions[pcnt(msk)]){
       //  if (p.second < tot[p.first]) return false;
        if (p.second < pcnt( masks[p.first] & msk) ) return false;
    }
	return true;
}
//---------------------------------------------------------------------------------------------------

void _main() {
	cin >> N >> M;
    masks.resize(N+1,0);

    rep(i,0,N){
        masks[i+1] = (1<<i) | masks[i];
     //   cout << bitset<3>(masks[i+1]) << " " << bitset<3>(masks[i])<<endl;
    }

	rep(i, 0, M) {
		int X, Y, Z; cin >> X >> Y >> Z;
		restrictions[X].push_back({ Y, Z });
	}

	dp[0] = 1;
	rep(msk, 0, 1 << N) rep(nxt, 0, N) if (!(msk & (1 << nxt))) {
		if (check(msk + (1 << nxt))) dp[msk + (1 << nxt)] += dp[msk];
	}
	cout << dp[(1 << N) - 1] << endl;
}






#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll mod = 1e9 + 7;
const ll linf = 1LL << 62;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int N, M;
vector<pii> ms[20];
ll dp[1 << 18][20];
int cnt[1 << 18][20];
vector<int> to[1 << 18];
int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        ms[X].push_back({Y, Z});
    }
    for (int i = 0; i < (1 << N); i++) {
        for (int j = 0; j < N; j++) {
            if ((i >> j) & 1) {
                for (int k = j + 1; k <= N; k++) {
                    cnt[i][k]++;
                }
            } else {
                to[i].push_back(j);
            }
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < (1 << N); j++) {
            bool flag = true;
            for (auto u : ms[i]) {
                if (cnt[j][u.first] > u.second) flag = false;
            }
            if (flag) {
                for (auto u : to[j]) {
                    dp[j | (1 << u)][i + 1] += dp[j][i];
                }
            } else {
                dp[j][i] = 0;
            }
        }
    }
    cout << dp[(1 << N) - 1][N] << endl;
}