#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,u[10],v[10],w[10];
int e[10][10],p[10][10],cnt[10];
const int M=1e9+7;
int gcd(int u,int v){
  if (u<v)swap(u,v);
  if (v==0)return u;
  return gcd(v,u%v);
}
int ksm(int u,int v){
  if (v==0)return 1;
  if (v&1)return ksm(u,v^1)*u%M;
  int k=ksm(u,v>>1);
  return k*k%M;
}
void add(int u,int v,int w){
    e[u][++cnt[u]]=v;
    p[u][cnt[u]]=w;
}
int dis[10];
int cal(int s){
  int ans=0;
  memset(dis,0x3f,sizeof(dis));
  dis[s]=0;
  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
  q.push({0,s});
  while (!q.empty()){
    int u=q.top().second;q.pop();
    ans+=dis[u];dis[u]=0;
    for (int i=1;i<=cnt[u];i++){
      int v=e[u][i],w=p[u][i];
      if (dis[v]>w){
	dis[v]=w;
	q.push({w,v});
      }
    }
  }
  for (int i=1;i<=n;i++){
    if (dis[i])return 0x3f3f3fff;
  }
  return ans;
}
void solve(){
  cin>>n>>m;
  for (int i=1;i<=m;i++){
    cin>>u[i]>>v[i]>>w[i];
  }
  int ans=0,mim=0x3f3f3f3f;
  for (int i=0;i<(1<<m+m);i++){
    for (int i=1;i<=n;i++)cnt[i]=0;
    for (int j=0;j<m+m;j++){
      if (i&(1<<j)){
	if (j&1)add(u[j/2+1],v[j/2+1],w[j/2+1]);
	else add(v[j/2+1],u[j/2+1],w[j/2+1]);
      }
    }
    for (int j=1;j<=n;j++){
      int res=cal(j);
      if (res<mim){
	ans=1;
	mim=res;
      }
      else if (res==mim)ans++;
      if (cal(j)<0x3f3f3f3f)break;
    }
  }
  int p=ans,q=1<<m+m;
  int k=gcd(p,q);
  p/=k,q/=k;
  cout<<p%M*ksm(q,M-2)%M<<"\n";
}
signed main(){
  freopen("years.in","r",stdin);
  freopen("years.out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);
  int c,t;
  cin>>c>>t;
  while (t--){
    solve();
  }
  return 0;
}