#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

///#pragma comment(linker,"/STACK:102400000,102400000")   à&#169;&#213;&#187;
#define clr(s,x) memset(s,x,sizeof(s))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lowbit(x) (x&(-x))
#define PB push_back
#define For(i,a,b) for(int i=a;i<b;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

typedef long long               LL;
typedef unsigned int            uint;
typedef unsigned long long      ULL;
typedef vector<int>             vint;
typedef vector<string>          vstring;

void RI (int& x){
    x = 0;
    char c = getchar ();
    while (c == ' '||c == '\n')    c = getchar ();
    bool flag = 1;
    if (c == '-'){
        flag = 0;
        c = getchar ();
    }
    while (c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = getchar ();
    }
    if (!flag)    x = -x;
}
void RII (int& x, int& y){RI (x), RI (y);}
void RIII (int& x, int& y, int& z){RI (x), RI (y), RI (z);}


const double e   = 2.718281828459045;
const double PI  = acos(-1.0);
const int maxn   = 20;
const int maxm   = 1e5 + 100;
const LL mod     = 1e9 + 7;
const double eps = 1e-9;
const int INF    = 0x3f3f3f3f;

/************************************END DEFINE*********************************************/

int dis[maxn][maxn],dp[maxn][1<<16];
int n,m;
int T;

int main()
{
    RI(T);
    while(T--){
        RII(n,m);
        For(i,0,n)
            For(j,0,n)
                if(i!=j) dis[i][j]=INF;
                else dis[i][j]=0;

        while(m--){
            int u,v,w;
            RIII(u,v,w);
            u--;
            v--;
            dis[u][v]=dis[v][u]=min(w,dis[u][v]);
        }

        if(n==1){
            printf("%d\n",0);
            continue;
        }
        For(k,0,n)
            For(i,0,n)
                For(j,0,n)
                    if(dis[i][k]+dis[k][j]<dis[i][j])
                        dis[i][j]=dis[i][k]+dis[k][j];

        int sum=(1<<n);
        For(i,0,n)
            for(int sts=0;sts<sum;sts++)
                dp[i][sts]=1000000;
        dp[0][0]=0;
        For(i,0,n)
            dp[i][1<<i]=dis[0][i];

        for(int sts=1;sts<sum;sts++)
            For(i,0,n){
                if(sts&(1<<i)){
                    For(j,0,n){
                        if((sts&(1<<j))==0)
                            dp[j][sts|(1<<j)]=min(dp[j][sts|(1<<j)],dp[i][sts]+dis[i][j]);
                    }
                }
            }

        printf("%d\n",dp[0][sum-1]);
    }
    return 0;
}