//#pragma comment(linker,"/STACK:102400000,102400000")
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define ll long long
#define db double
#define PB push_back
#define lson k<<1
#define rson k<<1|1
using namespace std;

const int N = 20;
const int INF = 1000000000;

int mp[N][N];
int f[1<<16][16];

int main()
{
#ifdef PKWV
//    freopen("in.in","r",stdin);
#endif // PKWV
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) mp[i][j]=(i==j)?0:INF;
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            u--,v--;
            mp[u][v]=mp[v][u]=min(w,mp[u][v]);
        }
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
        for(int i=0;i<(1<<n);i++)
            for(int j=0;j<n;j++) f[i][j]=INF;
        f[1][0]=0;
        for(int i=1;i<n;i++) f[1][i]=INF;
        for(int i=1;i<(1<<n);i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)
                {
                    if((i>>k)&1){}
                    else 
                    {
                        f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+mp[j][k]);
                    }
                }
            }
        }
        int ans(INF);
        for(int i=0;i<n;i++)
            ans=min(ans,f[(1<<n)-1][i]+mp[i][0]);
        printf("%d\n",ans);
    }
    return 0;
}