#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
const int N = 100010;
const int mod = 998244353;
map<pair<int, int>, int> w;
int n, m;
long long remain;
int down[N][2], left[N][2], on[N];
int f[2][1 << 4];
bool can[1<<4];
int add(int x, int y) {
    x+= y;
    return x >= mod ?x - mod : x;
}
int sub(int x, int y) {
    x -= y;
    return x < 0 ? x +mod : x;
}
int mul(int x, int y){
    return 1ll * x * y % mod;
}
int calc(int x, long long y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x), y >>= 1;
    }
    return z;
}
int index(int s, int x){return (((s) >> x) & 1);}
int take(int s) {return (index((s), 3) | (index((s), 5)<<1 ) | (index((s), 7) << 2) | (index((s), 6) << 3));}
bool obey_map(int x, int s) {
    return !((down[x][0] && down[x][0] - 1 != index(s, 2))||(left[x][0] && left[x][0] - 1 != index(s, 1))|| (on[x] && on[x] - 1 != index(s, 0)) || (on[x + 1] && on[x + 1] - 1 != index(s, 3)));
}
bool obey_map3(int x, int s) {
    return obey_map(x, s) && obey_map(x + 1, take(s)) && !((down[x][1] && down[x][1] - 1 != index(s, 8))||(left[x][1] && left[x][1] - 1 != index(s, 4)));
}
bool check_rules(int s) {
    return !(__builtin_popcount(s) & 1);
}
int main() {
    scanf("%d %d", &n, &m);
    remain = 1ll * n * n - 2 * 2 - 5 * (n - 2);
    bool is_zero = 0;
    while (m -- ){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        if (x == y)
            on[x] = z + 1;
        else {
            if (x - 1 == y)
                down[y][0] = z + 1;
            else
            {
                if (x - 2 == y)
                    down[y][1] = z + 1;
                else {
                        if (y - 1 == x)
                            left[x][0] = z + 1;
                        else
                        {
                            if (y - 2 == x)
                                left[x][1] = z + 1;
                            else {
                                w[make_pair(x, y)] = z;
                                auto u = w.find(make_pair(y, x));
                                if (u != w.end() && u->second != z)
                                    is_zero = 1;
                                if (u == w.end()) {
                                    remain -= 2;
                                }
                            }
                        }
                    }
            }
        }
    }
    if (is_zero) {
        puts("0");
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < 4; i ++)
        for (int j = i + 1; j < 4; j ++)
            can[(1 << i) |(1 << j)] = 1;
    can[15] = 1;
    can[0]  =1;
    for (int i = 0; i < (1 << 4); i ++)
        if (obey_map(1, i) && can[i]) {
            f[0][i] = 1;
            ans ++;
        }
    if (n == 2) {
        printf("%d\n", ans);
        return 0;
    }
    bool bz =  0, bz1 = 1;
    for (int i = 1; i + 2 <= n; i ++, swap(bz, bz1))
        for (int j = 0; j < (1 << 4); j ++)
            if (f[bz][j]) {
                for (int k = 0; k < (1 << 5); k ++)
                    if (obey_map3(i, j | (k << 4)) && check_rules(j | (k << 4)) &&can[take(j | (k << 4))])
                        f[bz1][take(j | (k << 4))] = add(f[bz1][take(j | (k << 4))], f[bz][j]);
                f[bz][j] = 0;
            }
    ans = 0;
    for (int i = 0; i < (1 << 4); i ++)
        ans = add(ans, f[bz][i]);
    ans = mul(ans, calc(2, remain / 2));
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 3328