#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=1e5+5;
int n,m;ll ans=0;
set<int> edg[MAXN][2];vector<int> chn;
int p[MAXN],c[MAXN],tot,cnt;bool vis[MAXN];
struct node{int mn,cnt;};
node operator +(node x,node y){
node z;
z.mn=min(x.mn,y.mn);z.cnt=0;
if(z.mn==x.mn) z.cnt+=x.cnt;
if(z.mn==y.mn) z.cnt+=y.cnt;
return z;
}
void operator +=(node &x,int y){
x.mn+=y;
}
struct segt{
node val[MAXN<<2];int laz[MAXN<<2];
void build(int id=1,int l=0,int r=m-1){
laz[id]=0;
if(l==r) {val[id]=(node){l,1};return;}
int mid=l+r>>1;
build(id<<1,l,mid);build(id<<1|1,mid+1,r);
val[id]=val[id<<1]+val[id<<1|1];
}
void pushdown(int id){
laz[id<<1]+=laz[id],laz[id<<1|1]+=laz[id];
val[id<<1]+=laz[id];val[id<<1|1]+=laz[id];
laz[id]=0;
}
void add(int L,int R,int x,int id=1,int l=0,int r=m-1){
if(L>R) return;
if(L<=l&&r<=R){
laz[id]+=x;val[id]+=x;
return;
}
pushdown(id);
int mid=l+r>>1;
if(L<=mid) add(L,R,x,id<<1,l,mid);
if(mid<R) add(L,R,x,id<<1|1,mid+1,r);
val[id]=val[id<<1]+val[id<<1|1];
}
node ask(int L,int R,int id=1,int l=0,int r=m-1){
if(L<=l&&r<=R) return val[id];
pushdown(id);
int mid=l+r>>1;
if(R<=mid) return ask(L,R,id<<1,l,mid);
if(mid<L) return ask(L,R,id<<1|1,mid+1,r);
return ask(L,R,id<<1,l,mid)+ask(L,R,id<<1|1,mid+1,r);
}
}T;
void dfs(int u,int fa){
p[u]=++tot;c[u]=cnt;
for(int v:edg[u][0]) if(v!=fa){
dfs(v,u);
}
}
void dfs1(int u,int fa){
chn.push_back(u);vis[u]=true;
for(int v:edg[u][1]) if(!vis[v]){
dfs1(v,u);
}
}
void solve(){
static int stl[MAXN],str[MAXN],topl,topr,l;
topl=topr=0;stl[0]=str[0]=-1;
m=chn.size(),l=0;T.build();
if(m==2){
ans+=2+edg[chn[0]][0].count(chn[1]);
return;
}
for(int i=0;i<m;i++){
if(i!=0&&c[chn[i]]!=c[chn[i-1]]) l=i;
int lst=i;
while(topl&&p[chn[stl[topl]]]>p[chn[i]]){
T.add(stl[topl-1]+1,lst-1,p[chn[stl[topl]]]-p[chn[i]]);
lst=stl[topl-1]+1,topl--;
}
stl[++topl]=i;
lst=i;
while(topr&&p[chn[str[topr]]]<p[chn[i]]){
T.add(str[topr-1]+1,lst-1,p[chn[i]]-p[chn[str[topr]]]);
lst=str[topr-1]+1,topr--;
}
str[++topr]=i;
ans+=T.ask(l,i).cnt;
}
}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,c;cin>>u>>v>>c;
edg[u][c].insert(v);
edg[v][c].insert(u);
}
for(int i=1;i<=n;i++) if(edg[i][0].empty()||edg[i][1].empty()){
for(int j:edg[i][0]) edg[j][0].erase(i);
for(int j:edg[i][1]) edg[j][1].erase(i);
edg[i][0].clear();edg[i][1].clear();
}
for(int i=1;i<=n;i++) if(edg[i][0].size()<=1&&!p[i]) cnt++,dfs(i,0);
for(int i=1;i<=n;i++) if(!p[i]) p[i]=MOD;
for(int i=1;i<=n;i++) if(edg[i][1].size()<=1&&!vis[i]){
chn.clear();dfs1(i,0);
solve();
}
for(int i=1;i<=n;i++) if(!vis[i]){
chn.clear();dfs1(i,0);
m=chn.size();ans+=3*m/2;
}
cout<<ans%998244353<<'\n';
return 0;
}