//边全部不相等非常好做

//全为 1 似乎启发我们拆开每种颜色的边分别考虑？

//计数启动！

#include<bits/stdc++.h>

#define vi vector<ll>
#define pi pair<ll,ll>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define For(i,j,k) for(ll i=(j);i<=(k);i++)
#define Fol(i,j,k) for(ll i=(j);i>=(k);i--)
#define IL inline
#define ll long long

using namespace std;

#define N 500005
#define M 31
#define mod 1000000007

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

int pls(int x,int y){return (x+y>=mod?x+y-mod:x+y);}
int sub(int x,int y){return (x-y<0?x-y+mod:x-y);}
void Add(int &x,int y){x=pls(x,y);}
void Dec(int &x,int y){x=sub(x,y);}
int mul(int x,int y){return x*1ll*y%mod;}
int qp(int x,int y=mod-2){int ans=1;while(y){if(y&1)ans=mul(ans,x);x=mul(x,x);y>>=1;}return ans;}

int pw[N];
struct Node{
    int u,v,w;
    Node(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
}P[N];
int c;

namespace subC{

    basic_string<int> e[N];

    int c,T;
    int E[N],a[M][M],f[N],tmp[N],g[N],h[N];

    void solve(){
        int n=read(),m=read();
        memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(E,0,sizeof(E));memset(tmp,0,sizeof(tmp));
        memset(a,0,sizeof(a));
        For(i,1,m){
            P[i].u=read(),P[i].v=read(),P[i].w=read();
            e[P[i].u]+=P[i].v;e[P[i].v]+=P[i].u;
            a[P[i].u][P[i].v]=a[P[i].v][P[i].u]=1;
        }
        For(S,1,(1<<n)-1){
            if(__builtin_popcount(S)==1)continue;
            int lb=(S&(-S)),T=S^lb,id=__lg(lb)+1;E[S]=E[T];
            For(j,1,n)if((S&(1<<(j-1))) && (1<<(j-1))!=lb)E[S]+=a[id][j];
        }
        g[0]=mod-1;f[0]=1;
        int inv2=(mod+1)/2;
        For(S,1,(1<<n)-1){
            if(__builtin_popcount(S)==1){f[S]=1;g[S]=1;continue;}
            for(int T=(S&(S-1));T;T=S&(T-1)){
                if((T&(-T))!=(S&(-S)))continue;
                Add(g[S],mul(mul(f[T],g[S^T]),mod-1));
            }
            tmp[S]=1;
            for(int T=S;T;T=S&(T-1)){
                int U=T^S;
                if(U!=0){
                    int lb=(U&(-U)),id=__lg(lb)+1;
                    tmp[T]=tmp[T^lb];
                    For(j,1,n){
                        if(j==id)continue;
                        if((1<<(j-1))&T)tmp[T]=mul(tmp[T],a[id][j]*2);
                        else if((1<<(j-1))&S)tmp[T]=mul(tmp[T],a[id][j]*inv2);
                    }
                }
                Add(f[S],mul(mul(pw[E[S^T]],g[T]),tmp[T]));   
            }
            f[S]=sub(qp(4,E[S]),f[S]);Add(g[S],f[S]);
        }
        cout<<(mod+1)/2<<endl;
        //For(S,1,(1<<n)-1)g[S]=Dec()
    }
}

namespace subB{
    struct UN{
        int f[N],siz[N];
        int find(int x){return (x==f[x]?x:f[x]=find(f[x]));}
        void merge(int x,int y){
            x=find(x);y=find(y);if(x==y)return;
            siz[y]+=siz[x];f[x]=y;
        }
        void init(int n){For(i,1,n)f[i]=i,siz[i]=1;}
    }U;
    int mark[N];
    void solve(){
        int n=read(),m=read();
        For(i,1,m)mark[i]=0;
        For(i,1,m)P[i].u=read(),P[i].v=read(),P[i].w=read();
        sort(P+1,P+m+1,[](Node x,Node y){return x.w<y.w;});U.init(n);
        For(i,1,m){
            int u=P[i].u,v=P[i].v;
            if(U.find(u)!=U.find(v))mark[i]=1,U.merge(u,v);
        }
        int inv4=qp(4),inv2=(mod+1)/2;
        int ans=0;
        For(S,1,(1<<n)-1){
            U.init(n);int flag=0;
            int lb=(S&(-S)),id=__lg(lb)+1;
            For(i,1,m){
                if(!mark[i])continue;
                if((S&(1<<(P[i].u-1))) && (S&(1<<(P[i].v-1)))){
                    U.merge(P[i].u,P[i].v);
                }
            }
            if(U.siz[U.find(id)]!=__builtin_popcount(S))continue;
            int coef=qp(inv4,__builtin_popcount(S)-1);
            coef=mul(coef,qp(inv2,(n-__builtin_popcount(S))));
            For(i,1,m){
                if(!mark[i])continue;
                if((S&(1<<(P[i].u-1))) && !(S&(1<<(P[i].v-1))))coef=mul(coef,inv2);
                else if(!(S&(1<<(P[i].u-1))) && (S&(1<<(P[i].v-1))))coef=mul(coef,inv2);
            }
            Add(ans,coef);
        }
        write(ans);putchar('\n');
    }
}

namespace subA{
    int n,m;
    int sta[10];
    basic_string<int> e[N];
    int vis[10];
    void dfs2(int x){
        vis[x]=1;
        for(auto v:e[x])if(!vis[v])dfs2(v);
    }
    int minnow;
    vi S;
    void dfs(int x,int cnt,int sum){
        if(sum>minnow)return;
        if(x>m){
            if(cnt!=n-1)return;
            For(i,1,n)e[i].clear();
            int U=0,w=1;
            For(i,1,m){
                U|=(w*sta[i]);w=w*4;
                if(sta[i]&1)e[P[i].u]+=P[i].v;
                if(sta[i]&2)e[P[i].v]+=P[i].u;
            }
            int fl=0;
            For(i,1,n){
                For(j,1,n)vis[j]=0;
                dfs2(i);int flag=1;
                For(j,1,n)flag&=vis[j];
                if(flag){fl=1;break;}
            }
            if(fl){
                if(sum<minnow)S.clear(),S.pb(U),minnow=sum;
                else if(sum==minnow)S.pb(U);
            }
            return;
        }
        For(i,0,3)sta[x]=i,dfs(x+1,cnt+(i!=0),sum+(i!=0)*P[x].w);
    }
    void solve(){
        n=read(),m=read();minnow=0x3f3f3f3f;S.clear();
        For(i,1,m)P[i].u=read(),P[i].v=read(),P[i].w=read();
        dfs(1,0,0);int ans=0;
        For(T,0,(1<<(2*m))-1){
            for(auto v:S)if((T&v)==v){ans++;break;}
        }
        write(mul(qp(qp(4),m),ans));putchar('\n');
    }
}

int main(){
    freopen("years.in","r",stdin);
    freopen("years.out","w",stdout);
    pw[0]=1;For(i,1,N-1)pw[i]=mul(2,pw[i-1]);
    c=read();int T=read();
    while(T--){
        if(c<=3 || c>17)subA::solve();
        else if(c>=4 && c<=6)subB::solve();
        else if(c>=7 && c<=16)subC::solve();
    }
    return 0;
}

//Wish us good luck!