#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<random>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define cht 1000000007
#define IV void
#define her1 200812124
#define ull unsigned long long
#define mem(x,val) memset(x,val,sizeof x)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 1e2+5;
const i64 inv2 = (cht+1>>1);
IV cadd(i64&x,i64 val){x=(x+val)%cht;}
const int MAX = 1e3;
i64 coef[30],pw[1005];
IV init(){
	pw[0]=1;F(i,1,MAX)pw[i]=pw[i-1]*inv2%cht;
	F(i,0,29){
		coef[i]=(1<<i)-1;
		F(j,0,i)coef[i]=coef[i]*inv2%cht;
	}
}
pair<i64,i64>pi[maxn];i64 n,m;
namespace Subtask1{
	i64 u[maxn],v[maxn],w[maxn],du[maxn];
	i64 x[maxn],y[maxn],z[maxn],fa[maxn];
	i64 find(i64 x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	bool vis[1<<20];
	IV solve(){
		F(i,1,n)fa[i]=i;
		F(i,1,m)x[i]=read(),y[i]=read(),z[i]=read();
		vector<array<i64,3> >eg;
		F(i,1,m)eg.push_back({z[i],x[i],y[i]});
		sort(eg.begin(),eg.end());
		i64 sum=0;
		for(auto[w,u,v]:eg){
			u=find(u);v=find(v);
			if(u==v)continue;fa[u]=v;sum+=w;
		}
		F(i,1,m)F(k,0,1)u[2*i-k]=x[i],v[2*i-k]=y[i],w[2*i-k]=z[i];
		F(i,1,2*m)if(i&1)swap(u[i],v[i]);
		m*=2;i64 S=(1<<m)-1;
		F(s,0,S)vis[s]=0;
		F(s,0,S)if(__builtin_popcount(s)==n-1){
			i64 sw=0;
			F(i,1,n)fa[i]=i,du[i]=0;
			F(i,1,m)if(s>>i-1&1)
				fa[find(u[i])]=find(v[i]),sw+=w[i],du[v[i]]++;
			if(sw!=sum)continue;
			bool flag=1;
			F(i,1,n)flag&=(find(i)==find(1)&&du[i]<=1);
			if(!flag)continue;vis[s]=1;
		}
		F(i,1,m)F(s,0,S)if(s>>i-1&1)
			vis[s]|=vis[s^(1<<i-1)];
		i64 Ans=0;
		F(s,0,S)Ans+=vis[s];
		F(i,1,m)Ans=Ans*inv2%cht;
		printf("%lld\n",Ans);
	}
} // namespace Subtask1
i64 u[maxn],v[maxn],w[maxn],fa[maxn];
i64 find(i64 x){return fa[x]==x?x:fa[x]=find(fa[x]);}
namespace Subtask2{
	bool ve[25][25];
	vector<i64>G[25];
	IV solve(){
		F(i,0,n-1)fa[i]=i;
		vector<pair<i64,i64> >V;
		F(i,0,n-1)G[i].clear();mem(ve,0);
		F(o,1,m){
			i64 i=pi[o].second;
			i64 fu=find(u[i]),fv=find(v[i]);
			if(fu==fv)continue;fa[fu]=fv;i64 u=::u[i],v=::v[i];
			ve[u][v]=ve[v][u]=1;G[u].push_back(v);G[v].push_back(u);
		}
		i64 S=(1<<n)-1,Ans=0;
		F(s,1,S){
			F(i,0,n-1)fa[i]=i;
			F(i,0,n-1)F(j,0,n-1)if(s>>i&1)if(s>>j&1)if(ve[i][j])
				fa[find(i)]=find(j);
			i64 st=-1;
			bool flag=1;
			F(i,0,n-1)if(s>>i&1){
				if(st==-1)st=find(i);
				flag&=(st==find(i));
			}
			if(!flag)continue;
			i64 cnt=0,siz=0;
			F(i,0,n-1)if(s>>i&1)cnt+=(i64)G[i].size(),siz++;
			// cout<<cnt<<' '<<siz-1<<endl;
			cadd(Ans,pw[cnt-(siz-1)+n-1]);
		}
		printf("%lld\n",(Ans+cht)%cht);
	}
} // namespace Subtask2
namespace Subtask3{
	i64 dp[1<<15],bit[1<<15],val[1<<15][15],ve[20],f[1<<15];
	IV print(i64 v){
		v=(v%cht+cht)%cht;
		F(i,1,100)if(i*v%cht<=1e2)
			return(void)(cout<<i*v%cht<<'/'<<i<<endl);
	}
	IV solve(){
		mem(ve,0);i64 S=(1<<n)-1;F(s,0,S)dp[s]=0;dp[S]=1;
		F(i,1,m)ve[u[i]]|=(1<<v[i]),ve[v[i]]|=(1<<u[i]);
		F(s,1,S)bit[s]=bit[s>>1]+(s&1);
		F(s,0,S)F(i,0,n-1){
			i64 cnt=bit[s&ve[i]];
			val[s][i]=coef[cnt];
		}
		f[0]=0;
		F(s,1,S){
			i64 mx=31-__builtin_clz(s);f[s]=1;
			for(int t=s;t;(--t)&=s)if(t>>mx&1)if(s^t){
				i64 mul=-f[t];
				F(i,0,n-1)if(t>>i&1)
					mul=mul*val[s^t][i]%cht;
				cadd(f[s],mul);
			}
		}
		F(s,0,S)print(f[s]);
		D(s,S,0)for(int t=s;t;(--t)&=s)if(t!=s){
			i64 mul=dp[s]*((bit[t]&1)?-1:1);
			F(i,0,n-1)if(t>>i&1)
				mul=mul*val[s^t][i]%cht;
			cadd(dp[s^t],mul);
		}
		F(s,0,S)F(i,0,n-1)if(!(s>>i&1))
			dp[s]=dp[s]*pw[bit[ve[i]&s]]%cht;
		i64 Ans=0;
		F(s,1,S)cadd(Ans,f[s]);
		printf("%lld\n",(Ans+cht)%cht);
	}
} // namespace Subtask3

i64 id;
IV solve(){
	n=read();m=read();
	if(id<=3)return Subtask1::solve();
	F(i,1,m)u[i]=read()-1,v[i]=read()-1,pi[i]=make_pair(w[i]=read(),i);
	sort(pi+1,pi+1+m);
	bool flag=1;
	F(i,1,m-1)flag&=(pi[i].first!=pi[i+1].first);
	if(id<=6)return Subtask2::solve();
}
int main(){
	freopen("years.in","r",stdin);
	freopen("years.out","w",stdout);
	init();id=read();i64 T=read();while(T--)solve();return 0;
}