#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_S 50000
#define MAX_N 15
#define PRI 49993
#define OFFSET 3
#define MASK ((1 << OFFSET) - 1)
#define int long long
using namespace std;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
struct HashTable {
    int sz;
    int head[PRI], nxt[MAX_S];
    int sta[MAX_S], val[MAX_S];
    void clear() {
        memset(head, 0, sizeof(head));
        sz = 0;
    }
    void push(int s, int v) {
        int id = s % PRI;
        for (int i = head[id]; i; i = nxt[i]) {
            if (sta[i] == s) {
                val[i] += v;
                return;
            }
        }
        sta[++sz] = s, val[sz] = v;
        nxt[sz] = head[id], head[id] = sz;
    }
    void roll() {
        for (int i = 1; i <= sz; i++) {
            sta[i] <<= OFFSET;
        }
    }
} h[2], &h0 = h[0], &h1 = h[1];
int n, K;
int b[MAX_N];
int bn[MAX_N];
bool flag[MAX_N][MAX_N][4];
int encode() {
    memset(bn, -1, sizeof(bn));
    int s = 0, tot = 0;
    bn[0] = 0;
    for (int i = n; i >= 0; i--) {
        if (bn[b[i]] == -1) {
            bn[b[i]] = ++tot;
        }
        s = (s << OFFSET) | bn[b[i]];
    }
    return s;
}
void decode(int s) {
    for (int i = 0; i <= n; i++) {
        b[i] = s & MASK;
        s >>= OFFSET;
    }
}
void push(int j, int dn, int rt, int v) {
    b[j] = dn, b[j + 1] = rt;
    h1.push(encode(), v);
}
bool ok(int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; }
void setflag(int x, int y, int z) {
    flag[x][y][z] = true;
    if (z == 0) {
        if (ok(x, y + 1)) {
            flag[x][y + 1][2] = true;
        }
    } else if (z == 1) {
        if (ok(x + 1, y)) {
            flag[x + 1][y][3] = true;
        }
    } else if (z == 2) {
        if (ok(x, y - 1)) {
            flag[x][y - 1][0] = true;
        }
    } else {
        if (ok(x - 1, y)) {
            flag[x - 1][y][1] = true;
        }
    }
}
signed main() {
    cin >> n >> K;
    int x, y, z;
    for (int i = 1; i <= K; i++) {
        cin >> x >> y >> z;
        setflag(x - 1, y - 1, z - 1);
    }
    h1.clear();
    h1.push(0, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            swap(h0, h1);
            h1.clear();
            for (int k = 1; k <= h0.sz; k++) {
                decode(h0.sta[k]);
                int v = h0.val[k];
                int lt = b[j], up = b[j + 1];
                bool dn = i != n - 1 && !flag[i][j][1], rt = j != n - 1 && !flag[i][j][0];
                if (lt && up) {
                    if (!flag[i][j][2] && !flag[i][j][3]) {
                        if (lt == up) {
                            if (i == n - 1 && j == n - 1) {
                                push(j, 0, 0, v);
                            }
                        } else {
                            for (int i = 0; i <= n; i++) {
                                if (b[i] == lt) {
                                    b[i] = up;
                                }
                            }
                            push(j, 0, 0, v);
                        }
                    }
                } else if (lt || up) {
                    if ((lt && !flag[i][j][2]) || (up && !flag[i][j][3])) {
                        int t = lt | up;
                        if (dn) {
                            push(j, t, 0, v);
                        }
                        if (rt) {
                            push(j, 0, t, v);
                        }
                    }
                } else {
                    if (dn && rt) {
                        push(j, n, n, v);
                    }
                }
            }
        }
        h1.roll();
    }
    int ans = (h1.sz ? h1.val[1] : 0) << 1;
    if (ans) {
        cout << ans << endl;
    } else {
        cout << "orz" << endl;
    }
}