#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

template <int mod>
struct static_modint {
    using mint = static_modint;
    int x;

    static_modint() : x(0) {}
    static_modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    mint& operator+=(const mint& rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        if ((x += mod - rhs.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        x = (int) (1LL * x * rhs.x % mod);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }

    mint pow(long long n) const {
        mint _x = *this, r = 1;
        while (n) {
            if (n & 1) r *= _x;
            _x *= _x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const { return pow(mod - 2); }

    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs.x == rhs.x;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs.x != rhs.x;
    }

    friend ostream &operator<<(ostream &os, const mint &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, mint &a) {
        int64_t t; is >> t;
        a = static_modint<mod>(t);
        return (is);
    }
};

const unsigned int mod = 998244353;
using modint = static_modint<mod>;
modint mod_pow(ll n, ll x) { return modint(n).pow(x); }
modint mod_pow(modint n, ll x) { return n.pow(x); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m; cin >> n >> m;
    vector<vector<pair<int,int>>> gg(n);
    for (int i = 0; i < m; ++i) {
        int x,y; cin >> x >> y;
        x -= 1; y -= 1;
        int z; cin >> z;
        gg[x].push_back({y, z});
        gg[y].push_back({x, z});
    }
    modint res = n;
    vector<vector<pair<int,int>>> g(n);
    set<pair<int,int>> st;
    vector<int> pa(n, -1);
    for (int i = 0; i < n; ++i) {
        sort(gg[i].begin(), gg[i].end());
        for (int j = 0; j < gg[i].size();) {
            int v = gg[i][j].first;
            int c = 0;
            while (j < gg[i].size() and gg[i][j].first == v) {
                c |= (1<<gg[i][j].second);
                j += 1;
            }
            if (c == 3) {
                pa[i] = v;
                if (i < v) {
                    res += 1;
                    st.insert({i, v});
                }
            }
            else {
                g[i].push_back({v, c});
            }
        }
    }
    modint four = 0;
    for (auto p : st) {
        int x = p.first, y = p.second;
        if (g[x].size()) {
            assert(g[x].size() == 1);
            int z = g[x][0].first;
            int c = g[x][0].second;

            if (g[z].size()) {
                bool ok = false;
                for (auto i : g[z]) {
                    if (i.first == y and c+i.second == 3) ok = true;
                }
                if (ok) res += 1;
            }
            if (pa[z] != -1) {
                z = pa[z];
                if (g[z].size()) {
                    assert(g[z].size() == 1);
                    if (g[z][0].first == y and c+g[z][0].second == 3) {
                        four += 1;
                    }
                }
            }
        }
    }
    res += four/2;
    {
        four = 0;
        for (int i = 0; i < n; ++i) {
            if (g[i].size() == 3) {
                int c = g[i][0].second;
                int cnt = 0;
                for (int j = 0; j < 3; ++j) {
                    if (g[i][j].second == c) cnt += 1;
                }
                int x = g[i][0].first;
                if (cnt == 2) {
                    for (int j = 0; j < 3; ++j) {
                        if (g[i][j].second != c) {
                            c = g[i][j].second;
                            x = g[i][j].first;
                            break;
                        }
                    }
                }
                {
                    if (g[x].size() == 3) {
                        cnt = 0;
                        for (int j = 0; j < 3; ++j) {
                            if (g[x][j].second == c) cnt += 1;
                        }
                        if (cnt == 2) {
                            int y = x;
                            for (int j = 0; j < 3; ++j) {
                                if (g[x][j].first != i and g[x][j].second == c) {
                                    y = g[x][j].first;
                                    break;
                                }
                            }
                            if (g[y].size() == 3) {
                                cnt = 0;
                                for (int j = 0; j < 3; ++j) {
                                    if (g[y][j].second == c) cnt += 1;
                                }
                                if (cnt == 2) {
                                    int z = y;
                                    for (int j = 0; j < 3; ++j) {
                                        if (g[y][j].first != x and g[y][j].second == c) {
                                            z = g[y][j].first;
                                            break;
                                        }
                                    }
                                    if (g[z].size() == 3) {
                                        cnt = 0;
                                        for (int j = 0; j < 3; ++j) {
                                            if (g[z][j].second == c) cnt += 1;
                                        }
                                        if (cnt == 1) {
//                                            cout << i << " " << x << " " << y << " " << z << endl;
                                            set<int> f = {i, x, y, z};
                                            auto check = [&](int x, int y, int z = -1) -> bool {
                                                set<int> stt = {x, y};
                                                if (z != -1) stt.insert(z);
                                                for (int j = 0; j < 3; ++j) {
                                                    if (g[x][j].second != c) stt.insert(g[x][j].first);
                                                }
                                                return (stt == f);
                                            };
                                            if (check(i,x) and check(x,i,y) and check(y,x,z) and check(z,y)) {
                                                four += 1;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
//        cout << four << endl;
        res += four/4;
    }
    cout << res << endl;
}