#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
int dp[65550][17];
struct cmp
{
    bool operator ()(int a,int b)
    {
        return dp[a%100000][a/100000]>dp[b%100000][b/100000];        
    }
};
int dis[20][20];
int n,m;
int bfs()
{
    memset(dp,127,sizeof(dp));
    priority_queue<int,vector<int>,cmp> q;
    int i,j;
    int t1,t2,t3,t4;
    q.push(1);
    dp[1][0]=0;
    while(!q.empty())
    {
        t1=q.top();
        q.pop();
        t2=t1/100000;
        t1%=100000;
        if(t1==(1<<n)-1&&t2==0) return dp[t1][t2];
        for(i=0;i<n;i++)
        {
            if(dis[t2][i]<=100&&dp[t1|(1<<i)][i]>dp[t1][t2]+dis[t2][i])
            {
                dp[t1|(1<<i)][i]=dp[t1][t2]+dis[t2][i];
                t3=(t1|(1<<i))+i*100000;
                q.push(t3);
            }
        }
    }
    return 0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dis,127,sizeof(dis));
        scanf("%d%d",&n,&m);
        int i,j;
        for(i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--;b--;
            dis[a][b]=min(c,dis[a][b]);
            dis[b][a]=min(c,dis[b][a]);
        }
        printf("%d\n",bfs());
    }
}