#include<bits/stdc++.h> #include<bits/extc++.h> #define ll long long #define ppc __builtin_popcountll using namespace std; const int N=1e5+10,M=65,mod=1e9+7; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} vector<int> E[M]; int f[M][M],C[M][M],du[M],x[M],y[M],w[M]; int fac[N]; int n,k; struct myhash{ll operator()(const ll &x)const{return x%mod;}}; __gnu_pbds::gp_hash_table<ll,int,myhash> DP[M],vis; void dfs(int dep,ll S){ //cout<<dep<<' '<<S<<endl; memset(f[dep],0,sizeof(f[dep])); if(vis[S]){ for(int i=0;i<=ppc(S);i++) f[dep][i]=DP[i][S]; return ; }vis[S]=1; int mx=-1,mxid=0; for(int i=1;i<=k;i++){ if((S>>(i-1))&1){ if(du[i]>mx) mx=du[i],mxid=i; } } if(mx<=0){ f[dep][0]=1; for(int i=1;i<=k;i++){ if((S>>(i-1))&1){ for(int j=ppc(S);j>=1;j--){ f[dep][j]=(f[dep][j]+1ll*f[dep][j-1]*w[i])%mod; } } } //cout<<"1:"<<dep<<' '<<S<<endl; //for(int i=0;i<=ppc(S);i++) cout<<f[dep][i]<<' ';cout<<endl; /*for(int i=0;i<=ppc(S);i++){ f[dep][i]=C[ppc(S)][i]; }*/ }else{ vector<int> v1,v2; for(auto x:E[mxid]){ if((S>>(x-1))&1) v1.push_back(x); } for(auto ed:v1)for(auto x:E[mxid]){ if((S>>(x-1))&1) v2.push_back(x); } ll ns=S^(1ll<<(mxid-1)); for(auto ed:v1) du[ed]--; dfs(dep+1,ns); for(auto ed:v1) du[ed]++,ns^=(1ll<<(ed-1)); for(int i=0;i<=ppc(S);i++) f[dep][i]=f[dep+1][i]; for(auto ed:v2) du[ed]--; dfs(dep+1,ns); //cout<<dep<<' '<<S<<endl; //for(int i=0;i<=ppc(S);i++) cout<<f[dep][i]<<' ';cout<<endl; for(auto ed:v2) du[ed]++; for(int i=1;i<=ppc(S);i++) f[dep][i]=(f[dep][i]+1ll*w[mxid]*f[dep+1][i-1])%mod; //cout<<dep<<' '<<S<<endl; //for(int i=0;i<=ppc(S);i++) cout<<f[dep][i]<<' ';cout<<endl; } for(int i=0;i<=ppc(S);i++) DP[i][S]=f[dep][i]; } int main(){ //freopen("matrix.in","r",stdin); //freopen("matrix.out","w",stdout); cin>>n>>k; for(int i=1;i<=k;i++) cin>>x[i]>>y[i]>>w[i]; for(int i=1;i<=k;i++) w[i]--; C[0][0]=1; for(int i=1;i<=k;i++){ C[i][0]=1; for(int j=1;j<=i;j++){ C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } } fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod; for(int i=1;i<=k;i++){ for(int j=1;j<=k;j++){ if(i==j) continue; if(x[i]==x[j]||y[i]==y[j]){ E[i].push_back(j); } } }for(int i=1;i<=k;i++) du[i]=E[i].size(); ll U=(1ll<<k)-1; dfs(1,U); int ans=0; for(int i=1;i<=k;i++){ //cout<<i<<' '<<f[1][i]<<endl; ans=(ans+1ll*f[1][i]*fac[n-i])%mod; }Add(ans,fac[n]); cout<<ans<<endl; return 0; }