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

int S, I;
int color[MAXS][MAXS];
int dp[MAXS][MAXS][3][4][4];
const bool DEBUG = false;

void printColor(){
    for(int i = 0; i < S; i++){
        for(int j = 0; j <= i; j++){
            cout << color[i][j] << " ";
        }
        cout << endl;
    }
}

int dfs(int r, int c, int col){
    if(DEBUG) cout << r << " " << c << " "<< col << endl;

    if(r >= S) return 0;
    if(c > r) return 0;
    int upleft =3, left = 3;
    if(r > 0){
        if(c > 0){
            upleft = color[r-1][c-1];
        }
    }
    if(c > 0){
        left = color[r][c-1];
    }
    if(r == 3){
        if(DEBUG) printColor();
    }
    //upleft -1
    if(dp[r][c][col][upleft][left] != -1){
        return dp[r][c][col][upleft][left];
    }
    if(color[r][c] != col && color[r][c] != -1){
        dp[r][c][col][upleft][left] = 0;
        return 0;
    }
    //cases upleft left and col are equal
    if(DEBUG)cout << "cheking upper left triangle\n";
    if(DEBUG) cout << "upleft: " << upleft << " left: " << left << " col: " << col<<endl; 
    if(!((upleft == 3) || (left == 3) || (upleft == left && left == col) || (upleft != left && left != col && col != upleft))){
        dp[r][c][col][upleft][left] = 0;
        return 0;
    }
    if(DEBUG) cout << "passed initial checks!" << endl;
    dp[r][c][col][upleft][left] = 1;
    if(c == S-1) return 1;
    bool changed = false;
    if(color[r][c] == -1){
        color[r][c] = col;
        changed = true;
    }
    int sum = 0;
    if(c == r){
        for(int i= 0; i < 3; i++){
            sum+=dfs(r+1,0,i);
        }
    }
    else{
        for(int i = 0; i < 3; i++){
            sum+=dfs(r,c+1,i);
        }
    }
    if(changed) color[r][c] = -1;
    return dp[r][c][col][upleft][left] = sum;
}

int main(){
    cin >> S >> I;
    fill(&color[0][0], &color[0][0] + sizeof(color)/4,-1);
    for(int i =0; i< I; i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        color[a][b] = c;
    }
    fill(&dp[0][0][0][0][0], &dp[0][0][0][0][0]+sizeof(dp)/4,-1);
    int ans = 0;
    for(int i = 0 ; i < 3; i++){
        ans+=dfs(0,0,i);
    }
    cout << ans << endl;
}