#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int MOD=1e9+7;
const int inv2=(MOD+1)/2;
namespace s3
{
	int u[10],v[10],w[10];
	int fa[10];
	int getfa(int x)
	{
		return x==fa[x]?x:fa[x]=getfa(fa[x]);
	}
	vector<int>g[10];
	bool vis[10];
	void dfs(int x)
	{
		if(vis[x]) return;
		vis[x]=1;
		for(int i=0;i<g[x].size();++i) dfs(g[x][i]);
	}
	bool res[(1<<12)+5];
	void solve()
	{
		int n,m;scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i) scanf("%d%d%d",u+i,v+i,w+i);
		for(int i=1;i<=m;++i)
			for(int j=i+1;j<=m;++j)
			{
				if(w[i]>w[j]) swap(u[i],u[j]),swap(v[i],v[j]),swap(w[i],w[j]);
			}
		for(int i=1;i<=n;++i) fa[i]=i;
		int s=0;
		for(int i=1;i<=m;++i)
		{
			int fx=getfa(u[i]),fy=getfa(v[i]);
			if(fx==fy)
			{
				continue;
			}
			fa[fx]=fy;
			s+=w[i];
		}
		int ans=0;
		memset(res,0,sizeof(res));
		for(int i=0;i<(1<<(2*m));++i)
		{
			if(__builtin_popcount(i)!=n-1) continue;
			for(int i=1;i<=n;++i) g[i].clear();
			int S=0;
			for(int j=1;j<=m;++j)
			{
				int x=i>>(2*j-2)&1;
				int y=i>>(2*j-1)&1;
				if(x) g[u[j]].push_back(v[j]),S+=w[j];
				if(y) g[v[j]].push_back(u[j]),S+=w[j];
			}
			if(S!=s) continue;
			bool flag=0;
			for(int i=1;i<=n;++i)
			{
				for(int j=1;j<=n;++j) vis[j]=0;
				dfs(i);
				flag=1;
				for(int j=1;j<=n;++j) flag&=vis[j];
				if(flag) break;
			}
			if(flag) res[i]=1;
		}
		for(int i=0;i<(1<<(2*m));++i)
		{
			for(int j=i;j>=0;j=i&(j-1))
			{
				res[i]|=res[j];
				if(j==0) break;
			}
			if(res[i]) ++ans;
		}
		for(int i=1;i<=2*m;++i) ans=ans*1ll*inv2%MOD;
		printf("%d\n",ans);
	}
}
namespace s6
{
	int u[200],v[200],w[200];
	int fa[20];
	int getfa(int x)
	{
		return x==fa[x]?x:fa[x]=getfa(fa[x]);
	}
	vector<int>g[20];
	bool vis[20];
	int f[20][(1<<15)+5];
	int h[(1<<15)+5];
	int n;
	void dfs(int x,int fa)
	{
		printf("%d %d\n",x,fa);
		int ct=g[x].size()-(x!=1);
		f[x][(1<<x-1)]=1;
		for(int i=0;i<g[x].size();++i)
		{
			int y=g[x][i];
			if(y==fa) continue;
			dfs(y,x);
			for(int j=0;j<(1<<n);++j) h[j]=f[x][j],f[x][j]=0;
			int tmp=1;
			for(int j=0;j<g[x].size();++j)
			{
				if(j==i||g[x][j]==fa) continue;
				for(int k=0;k<(1<<n);++k)
				{
					if(k>>g[x][j]-1&1)
					{
						tmp=tmp*2ll*f[g[x][j]][k]%MOD;
					}
				}
			}
			for(int j=0;j<(1<<n);++j)
			{
				//printf("%d %d\n",x,ct-1);
				f[x][j]=(f[x][j]+f[y][j]*1ll*tmp)%MOD;
			}
			for(int j=0;j<(1<<n);++j)
				for(int k=j;k>=0;k=(k-1)&j)
				{
					if(k>>y-1&1)
					{
						f[x][j]=(f[x][j]+h[j^k]*1ll*f[y][k])%MOD;
						f[x][j^k]=(f[x][j^k]+h[j^k]*1ll*f[y][k])%MOD;
					}
					if(k==0) break;
				}
		}
			for(int j=0;j<(1<<n);++j) if(f[x][j]) printf("%d %d %d\n",x,j,f[x][j]);
		//printf("%d %d %d\n",x,1,f[x][1]);
	}
	void solve()
	{
		int m;scanf("%d%d",&n,&m);
		for(int i=1;i<=m;++i) scanf("%d%d%d",u+i,v+i,w+i);
		for(int i=1;i<=m;++i)
			for(int j=i+1;j<=m;++j)
			{
				if(w[i]>w[j]) swap(u[i],u[j]),swap(v[i],v[j]),swap(w[i],w[j]);
			}
		for(int i=1;i<=n;++i) fa[i]=i;
		int s=0;
		int ct=0;
			for(int i=1;i<=n;++i) g[i].clear();
		for(int i=1;i<=m;++i)
		{
			int fx=getfa(u[i]),fy=getfa(v[i]);
			if(fx==fy)
			{
				continue;
			}
			fa[fx]=fy;
			s+=w[i];
			printf("a %d %d\n",u[i],v[i]);
			g[u[i]].push_back(v[i]);
			g[v[i]].push_back(u[i]);
		}
		memset(f,0,sizeof(f));
		int ans=0;
		dfs(1,0);
		for(int i=1;i<(1<<n);++i) ans=(ans+f[1][i])%MOD;
		for(int i=1;i<=2*n-2;++i) ans=ans*1ll*inv2%MOD;
		printf("%d\n",ans);
	}
}
int main()
{
	freopen("years.in","r",stdin);
	freopen("years.out","w",stdout);
	int C,T;scanf("%d%d",&C,&T);
	if(C<=3)
	{
		while(T--)
		{
			s3::solve();
		}
		return 0;
	}
	else
	{
		while(T--)
		{
			s6::solve();
		}
		return 0;
		
	}
	return 0;
}