#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<utility>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int M=25,N=(1<<18)+10;

int n,m,a[M];
vector<pair<int,int> > e[M];
ll dp[N];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back(make_pair(y,z));
	}
	dp[0]=1;
	for(int st=1;st<(1<<n);st++)
	{
		int X=0;
		for(int i=0;i<n;i++)
			if(st&(1<<i))X++;
		bool ff=true;
		for(int i=0;i<e[X].size();i++)
		{
			int y=e[X][i].first,z=e[X][i].second;
			int Z=0;
			for(int j=0;j<y;j++)
				if(st&(1<<j))Z++;
			if(Z>z)
			{
				ff=false;
				break;
			}
		}
		if(ff)
			for(int i=0;i<n;i++)
				if(st&(1<<i))
					dp[st]+=dp[st^(1<<i)];
	}
	printf("%lld",dp[(1<<n)-1]);
	return 0;
}
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
const int INF = 1e9;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < int(v.size()); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << ' ';
    }
    return os;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> MAX(n + 1, vector<int>(n));
    rep(i, n + 1) rep(j, n) MAX[i][j] = INF;
    rep(i, m) {
        int x, y, z;
        cin >> x >> y >> z;
        chmin(MAX[x][--y], z);
        // for (int j = y - 1; j < n; j++) chmin(MAX[x][j], z);
    }
    // rep(i, n) cout << MAX[i] << '\n';

    vector<ll> dp(1 << n);
    dp[0] = 1;
    vector<int> bits(1 << n);
    rep(i, 1 << n) bits[i] = i;
    sort(all(bits), [](int i, int j) {
        return __builtin_popcount(i) < __builtin_popcount(j);
    });
    for (int bit : bits) {
        int c = __builtin_popcount(bit);

        rep(nxt, n) if (~bit >> nxt & 1) {
            bool ok = 1;
            rep(j, n) {
                int cnt = 0;
                if (nxt <= j) cnt++;
                rep(k, j + 1) cnt += bit >> k & 1;
                ok &= cnt <= MAX[c + 1][j];
            }
            if (ok) dp[bit | 1 << nxt] += dp[bit];
        }
    }
    cout << dp[(1 << n) - 1] << '\n';
}