#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int N=16,M=250,inf=0x3f3f3f3f;
int tid,T;
int n,m;
int dx[M],dy[M],dz[M];
ll ksm(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int mp[N][N];
int dp[1<<N];
int get_min()
{
	for(int i=0;i<(1<<n);++i)
	{
		dp[i]=inf;
	}
	for(int i=0;i<n;++i)
	{
		dp[1<<i]=0;
	}
	for(int i=1;i<(1<<n);++i)
	{
		for(int j=0;j<n;++j)
		{
			if(i&(1<<j))
				continue ;
			int mn=inf;
			for(int k=0;k<n;++k)
			{
				if((i&(1<<k))&&mp[k][j])
				{
					mn=min(mn,mp[k][j]);
				}
			}
			/*if((i|(1<<j))==6)
				cout<<i<<" "<<j<<" "<<mn<<'\n';*/
			dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+mn);
		}
	}
	return dp[(1<<n)-1];
}
ll ans;
int minn;
void dfs(int x)
{
	if(x==m+1)
	{
		int mn=get_min();
		/*if(mn==inf)
		{
			for(int i=0;i<=2;++i)
			{
				for(int j=0;j<=2;++j)
				{
					if(mp[i][j])
						cout<<i<<" "<<j<<" "<<mp[i][j]<<'\n';
				}
			}
			puts("______");
		}*/
		if(mn==minn)
		{
			++ans;
		}
		else
		{
			if(mn<minn)
			{
				minn=mn;
				ans=1;
			}
		}
		return ;
	}
	mp[dx[x]][dy[x]]=dz[x];
	mp[dy[x]][dx[x]]=dz[x];
	dfs(x+1);
	mp[dx[x]][dy[x]]=0;
	dfs(x+1);
	mp[dx[x]][dy[x]]=dz[x];
	mp[dy[x]][dx[x]]=0;
	dfs(x+1);
	mp[dx[x]][dy[x]]=0;
	dfs(x+1);
}
void work1()
{
	memset(mp,0,sizeof(mp));
	ans=0;
	minn=inf;
	dfs(1);
	printf("%lld\n",ans*ksm(ksm(4,m),mod-2)%mod);
}

vector<int> to[N];
int fa[N],id[M];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
bool cmp(int x,int y)
{
	return dz[x]<dz[y];
}
int siz[N];
int get_cnt(int x,int ft,int mask,int zong)
{
	siz[x]=((mask>>x)&1);
	int num=0;
	for(int u:to[x])
	{
		if(u==ft)
			continue ;
		num+=get_cnt(u,x,mask,zong);
		siz[x]+=siz[u];
	}
	num+=(siz[x]!=0&&siz[x]!=zong);
	return num;
}
void work2()
{
	for(int i=0;i<n;++i)
	{
		to[i].clear();
	}
	for(int i=0;i<n;++i)
	{
		fa[i]=i;
	}
	for(int i=1;i<=m;++i)
	{
		id[i]=i;
	}
	sort(id+1,id+m+1,cmp);
	for(int i=1;i<=m;++i)
	{
		if(find(dx[i])!=find(dy[i]))
		{
			to[dx[i]].push_back(dy[i]);
			to[dy[i]].push_back(dx[i]);
			fa[find(dx[i])]=find(dy[i]);
		}
	}

	ans=0;
	for(int i=1;i<(1<<n);++i)
	{
		int tmp=__builtin_popcount(i);
		int w=get_cnt(0,-1,i,tmp);
		if(tmp&1)
		{
			ans=(ans+ksm(2,2*m-(n-1)-w))%mod;
		}
		else
		{
			ans=(ans-ksm(2,2*m-(n-1)-w)+mod)%mod;
		}
	}
	printf("%lld\n",ans*ksm(ksm(4,m),mod-2)%mod);
}
void work()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&dx[i],&dy[i],&dz[i]);
		--dx[i];
		--dy[i];
	}
	if(tid>=1&&tid<=3)
	{
		work1();
		return ;
	}
	if(tid>=4&&tid<=6)
	{
		work2();
		return ;
	}
}
int main()
{
	freopen("years.in","r",stdin);
	freopen("years.out","w",stdout);
	scanf("%d%d",&tid,&T);
	while(T--)
	{
		work();
	}
	return 0;
}