#define _CRT_SECURE_NO_WARNINGS
#include<list>
#include<queue>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=25;
const int M=40010;
const int mod=998244353;
typedef long long ll;
int n,m,tim,cnt,g[N][2];
bitset<25>f[1<<24|3];
ll h[1<<24|3];
vector<int>bitcnt[1<<24|3];

struct Graph{
	int tot,vis[N],col[N];
	vector<int>a[N][N];
	inline void lnk(int x,int y,int z){a[z][x].push_back(y);}

	inline bool dfs(int id,int x)
	{
		vis[x]=tim;
		g[cnt][col[x]]|=1<<x-1;
		for(auto y:a[id][x])
		{
			if(vis[y]!=tim)
				col[y]=col[x]^=1,dfs(id,y);
			else if(col[y]==col[x])
				return 0;
		}
		return 1;
	}
}e;

#define lowbit(x) ((x)&(-(x)))
inline int popcnt(int x)
{
	int res=0;
	while(x)res++,x^=lowbit(x);
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;i++)
		scanf("%d%d%d",&x,&y,&z),
		e.lnk(x,z,y),e.lnk(z,x,y);
	bool ans=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=cnt;j++)
			memset(g[j],0,sizeof(g[j]));
		tim++;cnt=0;
		for(int j=1;j<=n;j++)
			if(i!=j&&e.vis[j]!=tim)
			{
				cnt++;
				ans&=e.dfs(i,j);
				if(!ans)break;
			}
		for(int j=0,lim=1<<cnt;j<lim;j++)
		{
			int pos=0;
			for(int k=0;k<cnt;k++)
				pos|=g[k+1][j>>k&1];
			f[pos][i-1]=1;
		}
		if(!ans)break;
	}
	if(!ans){ puts("0");return 0; }

	//cout<<"!"<<endl;

	for(int i=0,lim=1<<n;i<lim;i++)
		bitcnt[popcnt(i)].push_back(i);
	h[0]=1;
	
	for(int i=0;i<n;i++)
		for(auto j:bitcnt[i])
			for(int k=0;k<n;k++)if(f[j][k])
				h[j|(1<<k)]=(h[j|(1<<k)]+h[j])%mod;
	printf("%lld\n",h[(1<<n)-1]);
	return 0;
}