#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 17
#define INF 0x3f3f3f3f
int dp[1<<MAXN][MAXN];
int dis[MAXN][MAXN];
void floyed(int n)
{
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                if(i==j||i==k||j==k) continue;
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dis,INF,sizeof(dis));
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            u--,v--;
            dis[u][v]=min(dis[u][v],w);
            dis[v][u]=dis[u][v];
        }
        for(int i=0;i<n;i++) dis[i][i]=0;
        floyed(n);
        memset(dp,INF,sizeof(dp));
        dp[(1<<n)-1][0]=0;
        for(int s=(1<<n)-1; s>=0; s--)
            for(int v=0; v<n; v++)
                for(int u=0; u<n; u++)
                    //if(!(s>>u&1))
                    dp[s][v]=min(dp[s][v],dp[s|1<<u][u]+dis[v][u]);
        printf("%d\n",dp[0][0]);
    }
    return 0;
}