#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
inline int qpow(int bas,int ind){
	int res=1;
	while(ind){
		if(ind&1) res=res*bas%mod;
		bas=bas*bas%mod;ind>>=1;
	}
	return res;
}
namespace A{
	int n,m;
	struct edge{
		int u,v,w;
	}a[505];
	int fa[25],g[7];
	inline bool cmp(edge x,edge y){
		return x.w<y.w;
	}
	int getf(int x){
		if(x==fa[x]) return x;
		return fa[x]=getf(fa[x]);
	}
	void solve(){
		int sum=0,ans=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++) fa[i]=i;
		for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
		sort(a+1,a+m+1,cmp);
		for(int i=1;i<=m;i++){
			int x=getf(a[i].u),y=getf(a[i].v);
			if(x==y) continue;
			fa[x]=y;
			sum+=a[i].w;
		}
		for(int p=0;p<(1<<(2*m));p++){
			for(int msk=1;msk<(1<<m);msk++){
				if(__builtin_popcount(msk)!=n-1) continue;
				int s=0;
				memset(g,0,sizeof(g));
				for(int i=1;i<=n;i++) g[i]=(1<<(i-1));
				for(int i=1;i<=m;i++)
					if((msk>>(i-1))&1){
						s+=a[i].w;
						int id1=(p>>(2*i-2))&1,id2=(p>>(2*i-1))&1;
						if(id1) g[a[i].u]|=1<<(a[i].v-1);
						if(id2) g[a[i].v]|=1<<(a[i].u-1);
					}
				if(s!=sum) continue;
				for(int k=1;k<=n;k++)
					for(int i=1;i<=n;i++)
						if((g[i]>>(k-1))&1) g[i]|=g[k];
				for(int i=1;i<=n;i++)
					if(g[i]==(1<<n)-1){
						ans++;
						goto nxt;
					}
			}
			nxt:;
		}
		ans=ans*qpow(qpow(4,m),mod-2)%mod;
		cout<<ans<<'\n';
	}
}
namespace B{
	struct edge{
		int u,v,w;
	}a[505];
	int fa[25],dp[(1<<15)+5],g[(1<<15)+5];
	vector<int> e[25];
	inline bool cmp(edge x,edge y){
		return x.w<y.w;
	}
	int getf(int x){
		if(x==fa[x]) return x;
		return fa[x]=getf(fa[x]);
	}
	void solve(){
		int n,m;
		memset(dp,0,sizeof(dp));
		cin>>n>>m;
		for(int i=1;i<=n;i++) fa[i]=i;
		for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
		sort(a+1,a+m+1,cmp);
		for(int i=1;i<=m;i++){
			int x=getf(a[i].u),y=getf(a[i].v);
			if(x==y) continue;
			fa[x]=y;
			e[a[i].u].push_back(a[i].v);
			e[a[i].v].push_back(a[i].u);
		}
		for(int i=1;i<=n;i++) dp[(1<<(i-1))]=1;
		for(int msk=1;msk<(1<<n);msk++)
			if(dp[msk])
				for(int j=1;j<=n;j++)
					if((msk>>(j-1))&1)
						for(int v:e[j]) dp[msk|(1<<(v-1))]=1;
		for(int i=1;i<(1<<n);i++) g[i]=n;
		for(int i=1;i<(1<<n);i++)
			if(dp[i])
				for(int j=i;j;j=(j-1)&i) g[j]=min(g[j],0ll+__builtin_popcount(i));
		int ans=0;
		for(int i=1;i<(1<<n);i++){
			int cnt=__builtin_popcount(i);
			if(cnt&1) ans=(ans+qpow(2,n-g[i]))%mod;
			else ans=(ans-qpow(2,n-g[i])%mod+mod)%mod;
		}
		ans=ans*qpow(qpow(4,n-1),mod-2)%mod;
		cout<<ans<<'\n';
	}
}
signed main(){
	freopen("years.in","r",stdin);
	freopen("years.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int c,T;
	cin>>c>>T;
	if(c<=3) while(T--) A::solve();
	else while(T--) B::solve();
	return 0;
}