#include<bits/stdc++.h>
#define il inline
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define tep(i,u) for(int i=head[u];i;i=e[i].nex)
#define fi first
#define se second
#define pb push_back
using namespace std;
il int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
const int N=16,MOD=1e9+7;
int qpow(int x,int k=MOD-2){
	int res=1;
	while(k){
		if(k&1) res=(ll)res*x%MOD;
		x=(ll)x*x%MOD; k>>=1;
	}return res;
}
struct edge{
	int u,v,w;
}e[N*N/2];
int fa[N],tr[100];
vector<int> g[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}int cnt;
void dfs(int u,int fa,int S){
	cnt++;
	for(int v:g[u]){
		if(v==fa) continue;
		if(S>>(v-1)&1) dfs(v,u,S);
	}
}
bool vis[N];int appp;
void dfs2(int u){
	if(vis[u]) return;
	vis[u]=1;appp++;
	for(int v:g[u]){
		dfs2(v);
	}
}
void solve(int C){
	int n=read(),m=read();
	rep(i,1,m){
		int u=read(),v=read(),w=read();
		e[i]={u,v,w};
	}
	sort(e+1,e+1+m,[](edge a,edge b){
		return a.w<b.w;
	});
	rep(i,1,n) fa[i]=i,g[i].clear();
	int tw=0;
	rep(i,1,m){
		int fx=find(e[i].u),fy=find(e[i].v);
		if(fx==fy) continue;
		fa[fx]=fy;tw+=e[i].w;
		g[e[i].u].pb(e[i].v);
		g[e[i].v].pb(e[i].u);
	}
	int inv4=qpow(4);
	if(C>=4&&C<=6){
		//B 性质： 
		//可以发现每个u->v 有 1/2 的概率有。 
		//显然不能枚举每条边的有无，因为总共是 2^2m 的。 
		//考虑b性质，则生成树唯一。可以直接找到其，然后为其找概率。 
		//考虑当前生成树中能到达全部点的点集。 不难发现若当前点集中的点若不在同一块，显然不可能。 
		//而每种情况的概率都是 (1/4)^{n-1}，找到所有的情况加起来即可。 
		int res=qpow(inv4,n-1),ans=0;
		Rep(S,1,1<<n){
			int b=__builtin_popcount(S);cnt=0;
			rep(i,1,n){
				if(S>>(i-1)&1){
					dfs(i,0,S);
					break;
				}
			}
			if(cnt!=b) continue;
			int pw=1;
			rep(i,1,n){
				if(S>>(i-1)&1) continue;
				for(int j:g[i]){
					if(S>>(j-1)&1) continue;
					if(i<j){
						pw=pw*2%MOD;
					}
				}
			}
			ans=(ans+(ll)res*pw%MOD)%MOD;
		}
		printf("%d\n",ans);
	}
	else {
		int tp=0,ans=0;
		Rep(S,0,1<<m){
			int b=__builtin_popcount(S);
			if(b!=n-1) continue;
			rep(i,1,n) fa[i]=i;
			int sumw=0,tot=n;
			rep(i,1,m){
				if(S>>(i-1)&1){
					int fx=find(e[i].u),fy=find(e[i].v);
					if(fx==fy) continue;
					fa[fx]=fy;tot--;sumw+=e[i].w;
				}
			}
			if(tot!=1||sumw!=tw) continue;
			tr[++tp]=S;
		}
		Rep(S,0,1<<m){
			Rep(T,0,1<<m){
				bool f=0;
				rep(i,1,tp){
					rep(j,1,n) g[j].clear();
					rep(j,1,m){
						if(tr[i]>>(j-1)&1){
							if(S>>(j-1)&1){
								g[e[j].u].pb(e[j].v);
							}
							if(T>>(j-1)&1){
								g[e[j].v].pb(e[j].u);
							}
						}
					}
					rep(j,1,n){
						rep(k,1,n) vis[k]=0;
						appp=0;
						dfs2(j);
						if(appp==n){
							f=1;
							break;
						}
					}
					if(f) break;
				}
				if(f) ans++;
			}
		}
		printf("%d\n",(ll)ans*qpow(inv4,m)%MOD);
	}
}
int main(){
	freopen("years.in","r",stdin);
	freopen("years.out","w",stdout);
	int c=read(),T=read();
	while(T--) solve(c);
	return 0;
}