#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
无语了，一场省选三个图论题
古典概率，直接方案数除以4^m就行了
考虑C性质
只需要有树就行了
考虑所有双向边，他们会使得这些连通块无论哪一个做根都是同一种方案
然后如果w[i]!=w[j]的话，估计只有一开始在MST上的边会被选择
*/
const int N=405,mo=1e9+7,inf=1e9;
inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=(res*a)%mo;
		a=(a*a)%mo;
		b>>=1;
	}
	return res;
}
int tc,T=1;
int n,m,omst,f[N],ans,head[N];
int fd(int x){return f[x]==x?x:f[x]=fd(f[x]);}
struct ege{
	int x,y,w;
	bool tag;
	bool operator<(const ege &T)const{
		return w<T.w;
	}
}oe[N];
int sum,ct;
struct egeo{int y,z;};
std::vector<egeo> g[N];
inline void add(int x,int y,int z){g[x].emplace_back(egeo{y,z});}
inline void del(int x){//删除x出去的最后一条边
	// head[x]=e[head[x]].nxt;
	g[x].pop_back();
}
bool vis[N];
int dis[N],kp,gf[N];
struct node{
	int x,id;
	bool operator<(const node &T)const{
		return x>T.x;
	}
};
priority_queue<node> q;
void bfs(int u){
	dis[u]=0;
	q.push(node{0,u});
	gf[u]=0;
	// cout<<u<<" - ";
	// int kp=0;
	while(q.size()){
		int x=q.top().id;q.pop();
		
		if(vis[x])continue;
		vis[x]=true;
		// cout<<x<<" ";
		kp+=gf[x];
		ct++;
		for(auto p:g[x]){
			int v=p.y,w=p.z;
			// cout<<v<<" "<<w<<"\n";
			if(dis[v]<=dis[x]+w)continue;
			dis[v]=dis[x]+w;
			gf[v]=w;
			// cout<<" <"<<v<<" ";
			// cout<<gf[v]<<"> ";
			q.push(node{dis[v],v});
		}
	}
	// cout<<kp<<"\n";
}
inline void chk(void){
	for(int i=1;i<=n;i++){//搞一个起点
		ct=kp=0;
		for(int j=1;j<=n;j++)vis[j]=false,dis[j]=inf;
		bfs(i);
		if(ct==n and kp==omst){ans++;return;}
	}
}
void dfs(int u){
	// if(sum>omst)return;
	if(u>m){chk();return;}
	int res=ans;
	dfs(u+1);
	// ans=(ans+(ans-res+mo))%mo;//我不使用其实答案是一样的
	if(oe[u].tag==false)return;

	// sum+=oe[u].w;
	add(oe[u].x,oe[u].y,oe[u].w);
	dfs(u+1);
	del(oe[u].x);

	add(oe[u].y,oe[u].x,oe[u].w);
	dfs(u+1);
	del(oe[u].y);

	add(oe[u].x,oe[u].y,oe[u].w);
	add(oe[u].y,oe[u].x,oe[u].w);
	dfs(u+1);
	del(oe[u].x),del(oe[u].y);

	// sum-=oe[u].w;
}
void solve1_3(void){
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)g[i].clear();
		for(int i=1;i<=m;i++)cin>>oe[i].x>>oe[i].y>>oe[i].w,oe[i].tag=true;
		sort(oe+1,oe+m+1);
		for(int i=1;i<=n;i++)f[i]=i;
		int ct=0;
		omst=0;
		for(int i=1;i<=m and ct<n-1;i++){
			int x=fd(oe[i].x),y=fd(oe[i].y);
			if(x==y)continue;
			ct++;
			omst+=oe[i].w;
			f[x]=y;
		}
		sum=0;
		ans=0;
		dfs(1);
		// cout<<ans<<"\n";
		(ans*=qpow(qpow(4,m),mo-2))%=mo;
		cout<<ans<<"\n";
	}
}
void solve4_6(void){
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)head[i]=0;
		for(int i=1;i<=m;i++)cin>>oe[i].x>>oe[i].y>>oe[i].w,oe[i].tag=false;
		sort(oe+1,oe+m+1);
		for(int i=1;i<=n;i++)f[i]=i;
		int ct=0;
		omst=0;
		for(int i=1;i<=m and ct<n-1;i++){
			int x=fd(oe[i].x),y=fd(oe[i].y);
			if(x==y)continue;
			oe[i].tag=true;
			ct++;
			omst+=oe[i].w;
			f[x]=y;
		}
		sum=0;
		ans=0;
		dfs(1);
		(ans*=qpow(qpow(4,n-1),mo-2))%=mo;
		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);
	cin>>tc>>T;
	if(tc<=3)solve1_3();
	else solve4_6();
}
/*
0 1
2 1
1 2 1
*/