#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int NN=1e9+7;
int n,m;
int f[100100];
vector<pair<int,int> >gg[100100];
int pp[100100],pt[100100],p2[100100];
int lowbit(int x){
    return x&(-x);
}
int mi(int x,int y){
    int sum=1;
    for (;y;y>>=1,x=x*x%NN)
    if(y&1)sum=sum*x%NN;
    return sum;
}
int ni2=(NN+1)>>1,ni4=mi(4,NN-2),ni3=mi(3,NN-2);
int g[100100][20];
int p[100100];
int c[1010][1010];
int ff[110];
int hh[100100],h[100100];
void solve(){
    cin>>n>>m;
    for (int i=0;i<n;i++)
    gg[i].clear();
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    for (int i=1,x,y,z;i<=m;i++)
    cin>>x>>y>>z,x--,y--,gg[x].push_back({y,z}),gg[y].push_back({x,z});
    int nn=1<<n;
    memset(hh,0,sizeof(hh));
    f[0]=1;
    p[0]=pp[0]=1;pt[0]=p2[0]=1;
    for (int i=1;i<=m;i++)p[i]=p[i-1]*ni2%NN,pp[i]=pp[i-1]*ni4%NN;
    // pt[i]=pt[i-1]*3*ni4%NN,p2[i]=p2[i-1]*ni3%NN;
    for (int i=1;i<nn;i++){
        hh[i]=1;
        for (int j=(i-1)&i;j;j=(j-1)&i){
            int ct=0;
            for (int kt=0;kt<n;kt++)
            if(j>>kt&1){
                for (auto kk:gg[kt])
                if((i^j)>>kk.first&1)ct++;
            }
            if(lowbit(j)==lowbit(i))
            hh[i]=(hh[i]-hh[j]*pp[ct])%NN;
        }
        // cout<<i<<" "<<(hh[i]*4*4*4%NN+NN)%NN<<"!!!\n";
    }
    // hh[7]=36*ni4%NN*ni4%NN*ni4%NN;
    for (int i=1;i<nn;i++){
        f[i]=hh[i];
        for (int j=(i-1)&i;j;j=(j-1)&i){
            int ct=0;
            for (int ii=(i^j);;ii=(ii-1)&(i^j)){
                h[ii]=0;
                if(!ii)break;
            }
            h[0]=1;
            // int ct=0;
            for (int k=0;k<n;k++)
            if(j>>k&1){
                for (auto kk:gg[k])
                if((i^j)>>kk.first&1){
                    int t=i^j;ct++;
                    for (int ii=t;;ii=(ii-1)&t){
                        if(ii>>kk.first&1)h[ii]=h[ii]*ni2%NN;
                        if(!ii)break;
                    }
                    for (int ii=t;;ii=(ii-1)&t){
                        if((ii>>kk.first&1)==0){
                            int tt=t^ii;
                            for (int jj=tt;jj;jj=(jj-1)&tt)
                            if(jj>>kk.first&1){
                                h[ii|jj]=(h[ii|jj]+h[ii]*ni4%NN*hh[jj])%NN;
                            }
                            h[ii]=h[ii]*ni4%NN;
                        }
                        if(!ii)break;
                    }
                    
                }
            }
            if(lowbit(j)<lowbit(i^j))f[i]=(f[i]-f[j]*h[i^j])%NN;
            else 
            f[i]=(f[i]-f[j]*f[i^j]%NN*(p[ct]-pp[ct]))%NN;
        }
        // cout<<i<<" "<<(f[i]*4*4*4%NN+NN)%NN<<"\n";
    }
    int ans=0;g[0][0]=1;
    c[0][0]=1;
    for (int i=1;i<=n;i++){
        c[i][0]=1;
        for (int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%NN;
    }
    memset(ff,0,sizeof(ff));
    for (int i=0;i<nn;i++)
    for (int j=0;j<=n;j++)
    if(g[i][j]!=0){
        // cout<<i<<" "<<j<<" "<<g[i][j]<<"\n";
        int t=(nn-1)^i;
        for (int k=t;k;k=(k-1)&t){
            int ct=0;
            for (int kt=0;kt<n;kt++)
            if(i>>kt&1){
                for (auto kk:gg[kt])
                if(k>>kk.first&1)ct++;
            }
            if(i==0||lowbit(i)>lowbit(k))
            g[i|k][j+1]=(g[i|k][j+1]+g[i][j]*f[k]%NN*pp[ct])%NN;
        }
        
        int tmp=g[i][j],ct=0;
        for (int k=0;k<n;k++)
        if(i>>k&1){
            for (auto kk:gg[k])
            if(i>>kk.first&1);
            else ct++;
        }
        tmp=tmp*p[ct]%NN;
        // cout<<i<<" "<<j<<" "<<(tmp*4*4*4%NN+NN)%NN<<"!!!!\n";
        ff[j]=(ff[j]+tmp)%NN;
    }
    for (int i=n-1;i>=1;i--)
    for (int j=i+1;j<=n;j++)
    ff[i]=(ff[i]-ff[j]*c[j][i])%NN;
    cout<<(ff[1]%NN+NN)%NN<<"\n";
    // for (int i=1;i<nn;i++){
    //     g[i]=1;
    //     for (int j=(i-1)&i;j;j=(j-1)&i){
    //         int ct=0;
    //         for (int k=0;k<n;k++)
    //         if(j>>k&1){
    //             for (auto kk:gg[j])
    //             if((i^j)>>kk.first&1)ct++;
    //         }
    //         if(lowbit(i)==lowbit(j))
    //         g[i]=(g[i]-g[j]*pp[ct])%NN;
    //     }
    // }
    // for (int i=1;i<nn;i++){
    //     f[i]=g[i];
    //     for (int j=(i-1)&i;j;j=(j-1)&i){
    //         ff[0]=1;
    //         for (int k=0;k<n;k++)
    //         if(j>>k&1){
    //             for (auto kk:gg[j])
    //             if((i^j)>>kk.first&1){
    //                 int tmp=i^j^(1<<kk.first);
    //                 for (int t=tmp;;t=(t-1)&tmp){
                        
    //                     if(!t)break;
    //                 }
    //             }
    //         }
    //         ff[i]
    //         for (int k=)
    //         // f[i]=(f[i]-f[j]*g[i^j]%NN*(p[ct]-pp[ct]))%NN;
    //     }
    // }


}
signed main(){
    freopen("years.in","r",stdin);
    freopen("years.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int c,T;
    cin>>c>>T;
    while(T--)solve();
}