#include<bits/stdc++.h>
// #define int long long
#define reg register
inline int read(){
    reg int x=0,k=1; reg char ch=getchar();
    while (ch<'0'||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); 
    return x*k;
}
const int N=1<<15|10,mod=1e9+7;
int n,m,C;
namespace sub{
    int f[N],g[N],mp[20],pw[N];
    int F[N],G[N][2];
    std::unordered_map<int,int> out[N];
    inline int get(reg int s,reg int t){
        reg int res=0;
        while (s) res+=__builtin_popcount(mp[std::__lg(s&-s)+1]&t),s^=s&-s;
        // for (reg int i=1;i<=n;i++) if (s>>i-1&1)
        return res;
    }
    inline void main(){
        n=read(),m=read();
        for (reg int i=1;i<=n;i++) mp[i]=0;
        for (reg int i=1;i<=m;i++){
            reg int u=read(),v=read(); read();
            mp[u]|=1<<v-1,mp[v]|=1<<u-1;
        }
        memset(f,0,(1<<n)<<2),memset(g,0,(1<<n)<<2);
        pw[0]=1; for (reg int i=1;i<=m+m;i++) pw[i]=(mod+1ll>>1)*pw[i-1]%mod;
        f[0]=1,g[0]=mod-1;
        for (reg int s=1;s<1<<n;s++){
            f[s]=1;
            for (reg int t=s;t;t=(t-1)&s) if (t!=s){
                reg int c=get(t,s^t);
                if ((t&-t)==(s&-s)) g[s]=(g[s]+mod-1ll*f[t]*g[s^t]%mod*pw[c+c]%mod)%mod; 
                f[s]=(f[s]+mod-1ll*pw[c]*g[s^t]%mod)%mod;
            }
            f[s]=(f[s]+mod-g[s])%mod,g[s]=(g[s]+f[s])%mod;
        }
        G[0][0]=mod-1;
        for (reg int s=1;s<1<<n;s++){
            G[s][0]=G[s][1]=0;
            for (reg int t=s;t;t=(t-1)&s) if ((t&-t)==(s&-s)){
                reg int c=pw[get(t,s^t)*2];
                G[s][0]=(G[s][0]+mod-1ll*f[t]*G[s^t][0]%mod*c%mod)%mod;
                G[s][1]=(G[s][1]+mod-1ll*f[t]*G[s^t][1]%mod*c%mod)%mod;
                G[s][1]=(G[s][1]+mod-1ll*f[t]*G[s^t][0]%mod*c%mod)%mod;
            }
        }
        reg int ans=0;
        for (reg int t=1;t<(1<<n);t++){
            reg int c=get((1<<n)-1^t,t);
            ans=(ans+1ll*pw[c]*G[t][1])%mod;
        }
        printf("%d\n",ans);
    }
}
namespace sub2{
    inline int qpow(reg int a,reg int b=mod-2){
        reg int res=1;
        for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) res=1ll*res*a%mod;
        return res;
    }    
    struct E{
        int u,v,w;
        inline bool operator<(const E &A)const{return w<A.w;}
    }e[N];
    int fa[N],S,mp[N];
    int find(reg int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    struct node{int v,w;};
    inline int check(reg int s,reg int t){
        if (__builtin_popcount(t)!=n-1) return 0;
        for (reg int i=1;i<=n;i++) mp[i]=0; reg int now=0;
        for (reg int i=1;i<=m;i++){
            if (t>>i-1&1) now+=e[i].w,mp[e[i].u]|=1<<e[i].v-1;
            if (t>>i+m-1&1) now+=e[i].w,mp[e[i].v]|=1<<e[i].u-1;
        }
        if (now!=S) return 0;
        for (reg int i=1;i<=n;i++) mp[i]|=1<<i-1;
        for (reg int j=1;j<=n;j++) for (reg int i=1;i<=n;i++) if (mp[i]>>j-1&1) mp[i]|=mp[j];
        // if (s==1) std::cerr<<"<< "<<t<<"\n";
        for (reg int i=1;i<=n;i++) if (mp[i]==(1<<n)-1) return 1;
        return 0;
    }
    inline void main(){
        n=read(),m=read();
        for (reg int i=1;i<=m;i++){
            e[i].u=read(),e[i].v=read(),e[i].w=read();
        }
        std::sort(e+1,e+m+1); S=0;
        for (reg int i=1;i<=n;i++) fa[i]=i;
        for (reg int i=1;i<=m;i++){
            reg int x=find(e[i].u),y=find(e[i].v);
            if (x!=y) S+=e[i].w,fa[x]=y;
        }
        reg int ans=0;
        for (reg int s=0;s<1<<m+m;s++){
            reg int flg=0;
            for (reg int t=s;t;t=(t-1)&s) flg|=check(s,t);
            flg|=check(s,0);
            // std::cerr<<"<< "<<s<<"\n";
            ans+=flg;
        }
        // std::cerr<<"<< "<<ans<<"\n";
        printf("%lld\n",1ll*ans*qpow(1<<m+m)%mod);
    }
}
namespace sub3{
    inline int qpow(reg int a,reg int b=mod-2){
        reg int res=1;
        for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) res=1ll*res*a%mod;
        return res;
    }    
    struct E{
        int u,v,w;
        inline bool operator<(const E &A)const{return w<A.w;}
    }e[N];
    int fa[N],S,mp[N],tot,pw[N];
    int find(reg int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    std::vector<int> G[N];
    bool dfs(reg int u,reg int s,reg int fa=0){
        reg int res=s>>u-1&1;
        for (auto v:G[u]) if (v^fa){
            res|=dfs(v,s,u);
        }
        if (res) tot++; return res;
    }
    inline void main(){
        n=read(),m=read();
        for (reg int i=1;i<=m;i++){
            e[i].u=read(),e[i].v=read(),e[i].w=read();
        }
        for (reg int i=1;i<=n;i++) G[i].clear();
        pw[0]=1; for (reg int i=1;i<=m+m;i++) pw[i]=(mod+1ll>>1)*pw[i-1]%mod;
        std::sort(e+1,e+m+1); S=0;
        for (reg int i=1;i<=n;i++) fa[i]=i;
        for (reg int i=1;i<=m;i++){
            reg int x=find(e[i].u),y=find(e[i].v);
            if (x!=y){
                S+=e[i].w,fa[x]=y;
                G[e[i].u].push_back(e[i].v),G[e[i].v].push_back(e[i].u);
            }
        }
        reg int all=0;
        for (reg int s=1;s<1<<n;s++){
            tot=0;
            for (reg int i=1;i<=n;i++) if (s>>i-1&1){dfs(i,s);break;}
            reg int now=pw[n-1+tot-1];
            if (__builtin_popcount(s)&1) all=(all+now)%mod; else all=(all+mod-now)%mod;
        }
        printf("%d\n",all);
    }
}
inline void work(){
    if (C<=3) return sub2::main(),void();
    if (C<=6) return sub3::main(),void();
    sub::main();
}
signed main(){
    freopen("years.in","r",stdin),freopen("years.out","w",stdout);
    C=read();
    for (reg int _=read();_--;) work();
    return 0;
}