#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcount using namespace std; typedef long long ll; typedef long double db; const int maxn=5e5+10,mod=998244353,iv2=(mod+1)/2; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; int jc[maxn],jc_inv[maxn],f[maxn]; inline int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1llu*a%mod; a=a*1llu*a%mod;b>>=1; }return res; } inline int C(int n,int m){return jc[m]*1llu*jc_inv[m-n]%mod*1llu*jc_inv[n]%mod;} void slv(){ n=read(),m=read(); jc[0]=jc_inv[0]=1;up(i,1,n)jc[i]=jc[i-1]*1llu*i%mod,jc_inv[i]=qp(jc[i],mod-2); int res=0; f[n]=1; int p=1;down(i,n-1,0){f[i]=(f[i+1]+C(p/2,n))%mod,p++;} int va=qp(iv2,n);up(i,0,n)f[i]=f[i]*1llu*va%mod; up(i,1,m){ int s=read(),t=read(),v=read(); res=(res+f[abs(s)+abs(s-t)]%mod*1llu*v)%mod; } cout<<res; } int main(){ //freopen("dejavu.in","r",stdin),freopen("dejavu.out","w",stdout); slv(); return 0; }