// 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;
}


vector<int> convolution(int siz, vector<int>& a, vector<int>& b){
    int n = (1 << siz);
    vector<int> c(n, 0);

    vector<int> a_subset = a;
    vector<int> b_subset = b;
    for(int i = 0; i < siz; ++i){
        for(int j = 0; j < n; ++j){
            if(!(j & (1 << i))){
                a_subset[j] += a_subset[j | (1 << i)];
                b_subset[j] += b_subset[j | (1 << i)];
            }
        }
    }
    for(int i = 0; i < n; ++i)
        c[i] = a_subset[i] * b_subset[i];

    for(int i = 0; i < siz; ++i){
        for(int j = 0; j < n; ++j){
            if(!(j & (1 << i)))
                c[j] -= c[j | (1 << i)];
        }
    }
    return c;
}


void solve(long long n, long long m, std::vector<long long> a, std::vector<long long> b){

    vector<vector<int>> v(n,vector<int>(n, 0));
    for(int i = 0; i < m; ++i){
        --a[i], --b[i];
        v[a[i]][b[i]] = 1;
    }
    vector<int> dp(1 << n, n);
    for(int i = 0; i < (1 << n); ++i){
        bool fl = true;
        for(int j = 0; j < n; ++j){
            for(int k = j + 1; k < n; ++k){
                if((i & (1 << j)) && (i & (1 << k)) && (!v[j][k]))
                    fl = false;
            }
        }
        if(fl)
            dp[i] = 1;
    }
    for(int i = 0; i < (1 << n); ++i){
        for(int j = i; j >= 0; j = (j - 1) & i){
            chmin(dp[i], dp[j] + dp[i ^ j]);
            if(!j)
                break;
        }
    }
    cout << dp.back() << endl;
}


signed main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <bits/stdc++.h>
using namespace std;

#define lson 2*i  
#define rson 2*i+1  
#define LS l,mid,lson  
#define RS mid+1,r,rson  
#define UP(i,x,y) for(i=x;i<=y;i++)  
#define DOWN(i,x,y) for(i=x;i>=y;i--)  
#define MEM(a,x) memset(a,x,sizeof(a))  
#define W(a) while(a)  
#define gcd(a,b) __gcd(a,b)  
#define ll long long  
#define MAX 1000005  
#define MOD 1000000007  
#define EXP 1e-8  
#define lowbit(x) (x&-x)  
// const int INF = 0x1fffffffffffffff;
const int INF = INT_MAX;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
void chmin(ll& a, ll b){ if(a > b) a = b; }
void chmax(ll& a, ll b){ if(a < b) a = b; }

int main () {
    int n, m; cin >> n >> m;
    int x, y, z;
    vector<vector<pair<int, int>>> cs(n+1);
    for (int i = 0; i < m; ++i){
        cin >> x >> y >> z;
        cs[x-1].emplace_back(y, z);
    }
    vector<ll> dp(1 << n);
    dp[0] = 1;
    queue<int> q;
    unordered_set<int> hash; 
    q.push(0);
    int pos = 0;
    while (!q.empty()) {
        int size = q.size(); 
        while (size--) {
            int state = q.front(); q.pop();
            for (int i = 0; i < n; ++i) {
                int num = (1 << i);
                if (state & num) continue;
                int newState = state | num;
                bool flag = true;
                for (auto &it : cs[pos]) {
                    y = it.first, z = it.second;
                    int mask = (1 << y) - 1;
                    if (__builtin_popcount(newState & mask) > z) {
                        flag = false; break;
                    }
                }
                if (flag) dp[newState] += dp[state];
                // cout << state << ' ' << newState << ' ' << dp[newState] << endl;
                if (!hash.count(newState))
                    q.push(newState), hash.insert(newState);
            }
        }
        // cout << pos <<endl;
        pos++;
    }
    cout << dp[(1<<n)-1] << endl;
    return 0;
}