#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
 
typedef pair<ll, ll> pl;
typedef pair<ld,ld> pd;
typedef vector<ll> vl;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
 
#define G(x) ll x; cin >> x;
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define all(a) begin(a), end(a)
#define K first
#define V second
#define OK(i,j) i >= 0 && i < n && j >= 0 && j < m
 
#define NN 2505
#define MM 5005
#define MOD 1000000007
#define M 3

ll powmod(ll x, ll y){
  ll r=1;
  while (y) {
    if (y%2) r = r*x%M;
    x = x*x%M;
    y/=2;
  }
  return r;
}

ll powmod(ll x, ll y, ll m) {
  ll r=1;
  while (y) {
    if (y%2) r = r*x%m;
    x = x*x%m;
    y/=2;
  }
  return r;
}

ll inv(ll a, ll b){return 1<a ? b - inv(b%a,a)*b/a : 1;}

ll inv(ll a) {return inv(a, M);}

typedef vector<vector<ll>> mat;

mat operator*(const mat &a, const mat &b) {
    mat c(a.size(), vector<ll>(b[0].size()));

    for (int i=0; i<a.size(); ++i)
        for (int k=0; k<b.size(); ++k)
            for (int j=0; j<b[0].size(); ++j)
                ( c[i][j] += a[i][k]*b[k][j] )%=M;
    return c;
}

mat operator+(mat a, const mat&b) {
    for (int i=0; i<a.size(); ++i)
        for (int j=0; j<a[0].size(); ++j)
            ( a[i][j] += b[i][j] )%=M;
    return a;
}

mat operator*(ll f, mat a) {
    for (int i=0; i<a.size(); ++i)
        for (int j=0; j<a[0].size(); ++j)
            ( a[i][j] *= f )%=M;
    return a;
}

mat operator*(const mat &a, ll f) {return f*a;}
mat operator/(const mat &a, ll f) {return a*inv(f);}
mat operator-(const mat &a){return a*(M-1);}
mat operator-(const mat &a, const mat &b) {return a + -b;}

mat transpose(const mat &a) {
    mat b(a[0].size(), vector<ll>(a.size()));
    for (int i=0; i<a.size(); ++i)
        for (int j=0; j<a[0].size(); ++j)
            b[j][i] = a[i][j];
    return b;
}

mat mat_id(int n) {
    mat a(n, vector<ll>(n));
    for (ll i=0; i<n; ++i) a[i][i]=1;
    return a;
}

mat exp_mat(const mat &x, ll y) {
    if (y==0) return mat_id(x.size());
    mat t = exp_mat(x, y/2);
    if (y%2) return t*t*x;
    return t*t;
}

// https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
vector<int> where;
int solve_system(mat &a, vector<ll> &b) {
    int n=a.size();
    int m=a[0].size();
    for (int i=0; i<n; ++i) a[i].push_back(b[i]);

    where.assign(m, -1);
    for (int col=0, row=0; col<m && row<n; ++col) {
        for (int i=row; i<n; ++i)
            if (a[i][col]) {
                swap(a[i], a[row]);
                break;
            }
        if (!a[row][col])
            continue;
        where[col] = row;

        for (int i=0; i<n; ++i)
            if (i != row) {
                ll c = a[i][col] * inv(a[row][col]) %M;
                for (int j=col; j<=m; ++j)
                    a[i][j] = ( a[i][j] - a[row][j]*c%M + M)%M;
            }
        ++row;
    }

    b.assign(m, 0);
    for (int i=0; i<m; ++i)
        if (where[i] != -1)
            b[i] = a[where[i]][m] * inv(a[where[i]][i]) %M;
    for (int i=0; i<n; ++i) {
        ll sum = 0;
        for (int j=0; j<m; ++j)
           ( sum += b[j] * a[i][j] )%=M;
        if (sum != a[i][m])
            return 0;
    }

    for (int i=0; i<m; ++i)
        if (where[i] == -1)
            return 2;
    return 1;
}

map<pl,ll> pair_to_ll;
map<ll,pl> ll_to_pair;

void solve() {
    
    ll S, I;
    cin >> S >> I;
    ll idx = 0;
    for(ll i=0;i<S;i++) {
        for(ll j=0;j<=i;j++) {
            pair_to_ll[{i,j}] = idx;
            ll_to_pair[idx] = {i,j};
            idx++;
        }
    }

    mat data(S*(S-1)/2);
    vector<ll> b(S*(S-1)/2);
    set<ll> given;
    map<ll,ll> color;
    for(ll i=0;i<S*(S-1)/2;i++) {
        b[i] = 0;
        for(ll j=0;j<S*(S+1)/2;j++) {
            data[i].push_back(0);
            if(j == i || j == pair_to_ll[{ll_to_pair[i].K+1,ll_to_pair[i].V}] || j == pair_to_ll[{ll_to_pair[i].K+1,ll_to_pair[i].V+1}]) data[i][j] = 1;
        }
    }

    // for(ll i=0;i<S*(S-1)/2;i++) {
    //     for(ll j=0;j<S*(S+1)/2;j++) {
    //         cout << data[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    ll u, v, cc;

    for(ll i=0;i<I;i++) {
        cin >> u >> v >> cc;
        u--; v--;
        ll c = pair_to_ll[{u,v}];
        if(given.count(c) > 0 && color[c] != cc) {
            cout << 0 << '\n';
            return;
        }
        given.insert(c);
        color[c] = cc;
        for(ll j=0;j<S*(S-1)/2;j++) {
            if(data[j][c] == 1) {
                data[j][c] = 0;
                b[j] = (b[j]+M-cc)%M;
            }
        }
    }

    int z = solve_system(data,b);
    if(z == 0) {
        cout << 0 << '\n';
        return;
    }

    // for(ll i=0;i<S*(S-1)/2;i++) {
    //     for(ll j=0;j<S*(S+1)/2;j++) {
    //         cout << data[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    ll i = 0, j = 0;
    ll ans = 1;
    while(i < S*(S-1)/2 && j < S*(S+1)/2) {
        if(given.count(j) > 0) j++;
        else if(data[i][j] == 0) {
            ans *= 3;
            j++;
        }
        else {
            i++;
            j++;
        }

    }

    while(j < S*(S+1)/2) {
        if(given.count(j) == 0) ans *= 3;
        j++;
    }

    cout << ans << '\n';
    

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    solve();

    return 0;

}