#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
long long n,m,k,l;
int f[1015][1015]={0},q[1015][1015]={0};
int main(){
	freopen ("tria.in","r",stdin);
	freopen ("tria.out","w",stdout);
	int a,b,c,d,e,g;
	cin>>n>>m;
	if(m==0)
	{
		if(n==3)
		{
			cout<<4;
			exit(0);
		}
		k=n*(n-1)%998244353;
		l=n*(n-3)%998244353;
		k+=l;
		k=k%998244353;
		cout<<k;
		exit(0);
	}
	int ans=0;
	if(n<=1000)
	{
		for(a=1;a<=n;a++)
			for(b=1;b<=n;b++)
				f[a][b]=2;
		for(a=1;a<=m;a++)
		{
			cin>>b>>c>>d;
			f[c][d]=b;
			f[d][c]=b;
		}
		for(a=1;a<=n;a++)
		{
			b=1+a;
			if(b>n)
			b=b%n;
			if(f[a][b]!=0)
			{
				c=b;
				for(d=1;d<=n-3;d++)
				{
					e=(c+d)%n;
					if(f[a][e]!=0&&f[b][e]!=0)
					{
						if(f[a][e]==2&&f[b][e]==2)
							ans++;
						if(f[a][b]!=1)
							q[a][b]=1;
						if(f[a][e]!=1)
							q[a][e]=1;
						if(f[b][e]!=1)
							q[b][e]=1;
					}
				}
			}
		}
		for(a=1;a<=n;a++)
		{
			for(b=1;b<=n;b++)
			{
				if(a!=b&&q[a][b]==1)
					ans++;
			}
		}
		cout<<ans;
		exit(0);
	}
	return 0;
}