#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;
		if(!p[i]){
			ans++;l=++i;
			topl=topr=0;
			continue;
		}
		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(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;
}