E-DsuRollback

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define BIT(i, x) (((x) >> (i) ) & 1)
#define task "cnt-mst"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 3e5 + 2;
const ll mod = 998244353;
int n, m, cnt(0);
vector<pair<int, int>> snap;
int par[N];
struct Edge
{
    int u, v;
    ll w;
    bool operator < (const Edge &a) const
    {
        return w < a.w;
    }
} s[N];

void Read()
{
    cin >> n;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
        cin >> s[i].u >> s[i].v >> s[i].w;
    sort(s + 1, s + m + 1);
}

int findpar(int v)
{
    return par[v] < 0 ? v : findpar(par[v]);
}

void Merge(int a, int b)
{
    if(par[a] < par[b])
        swap(a, b);
    --cnt;
    snap.emplace_back(a, par[a]);
    par[b] += par[a];
    par[a] = b;
}

void Rollback(int cur)
{
    while(cur--)
    {
        ++cnt;
        pair<int, int> a = snap.back();
        snap.pop_back();
        par[par[a.first]] -= a.second;
        par[a.first] = a.second;
    }
}

void Solve()
{
    memset(par, -1, sizeof par);
    ll ans = 1;
    cnt = n;
    for(int i = 1; i <= m; ++i)
    {
        int j = i;
        while(j <= m && s[j].w == s[i].w)
            ++j;
        int now = 0;
        for(int t = i; t < j; ++t)
        {
            int u = findpar(s[t].u),
                v = findpar(s[t].v);
            if(u != v)
                Merge(u, v),
                      ++now;
        }
        int cur = cnt;
        Rollback(now);
        ll res = 0;
        for(int t = 0; t < (1 << (j - i)); ++t)
        {
            now = 0;
            bool ck = 1;
            for(int h = i; h < j; ++h)
                if(BIT(h - i, t))
                {
                    int u = findpar(s[h].u),
                        v = findpar(s[h].v);
                    if(u != v)
                    {
                        Merge(u, v);
                        ++now;
                    }
                    else
                        ck = 0;
                }
            ck &= cnt == cur;
            if(ck) ++res;
            Rollback(now);
        }
        for(int t = i; t < j; ++t)
        {
            int u = findpar(s[t].u),
                v = findpar(s[t].v);
            if(u != v)
                Merge(u, v);
        }
        //cerr << cnt << "\n";
        ans = ans * res % mod;
        i = j - 1;
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".INP", "r"))
    {
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    Read();
    Solve();
}