与运算显然按位考虑，每次把当前枚举位i为1的边全部拿出来，那么这一位的总贡献就是2^i*生成树数量，生成树数量可以用矩阵树定理算出来。
最后把每一位的贡献加起来，除以所有边算出来的生成树数量。
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long a[33][105][105];
long long inv(long long x){return x==1?x:(mod-mod/x)*inv(mod%x)%mod;
}
long long cal(long long a[105][105],int n){for(int i=1;i<n;i++){for(int j=1;j<n;j++){if(a[i][j]<0)a[i][j]+=mod;if(a[i][j]>=mod)a[i][j]-=mod;}}for(int i=1;i<n;i++){if(a[i][i]==0){int flag=0;for(int j=i+1;j<n;j++){if(a[j][i]){for(int k=i;k<n;k++)a[i][k]=(a[i][k]+a[j][k])%mod;flag=1;break;}}if(!flag)return 0;}for(int j=i+1;j<n;j++){long long x=a[j][i]*inv(a[i][i])%mod;for(int k=i;k<n;k++){a[j][k]=(a[j][k]-x*a[i][k]%mod+mod)%mod;}}}long long ans=1;for(int i=1;i<n;i++)ans=ans*a[i][i]%mod;return ans;
}
int main(){int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=0;k<32;k++){a[k][i][j]=0;}}}for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);for(int j=0;j<=30;j++){if((w>>j)&1){a[j][u][u]++;a[j][v][v]++;a[j][u][v]--;a[j][v][u]--;}}a[31][u][u]++;a[31][v][v]++;a[31][u][v]--;a[31][v][u]--;}long long P=0,Q=cal(a[31],n);for(int i=0;i<=30;i++){P=(P+cal(a[i],n)*(1LL<<i)%mod)%mod;}printf("%lld\n",P*inv(Q)%mod);}
}