/*
*Rainto96
*Beijing University of Posts and Telecommunications School of Software Engineering
*http://blog.csdn.net/u011775691
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <climits>
using namespace std;
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define VINT vector<ll>
#define PII pair<ll,ll>
#define MP(x,y) make_pair((x),(y))
#define ll long long
#define ull unsigned ll
#define MEM0(x)  memset(x,0,sizeof(x))
#define MEM(x,val) memset((x),val,sizeof(x))
#define scan(x) scanf("%I64d",&(x))
#define scan2(x,y) scanf("%I64d%I64d",&(x),&(y))
#define scan3(x,y,z) scanf("%I64d%I64d%I64d",&(x),&(y),&(z))
#define scan4(x,y,z,k) scanf("%I64d%I64d%I64d%I64d",&(x),&(y),&(z),&(k))
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
using namespace std;
const ll INF= 0x3f3f3f3f3f3f3f3fLL;
ll n,m;
ll g[22][22];
const ll MAXN=17;
ll dp[1<<MAXN][MAXN];
struct Node{
        ll s;
        ll pos;
        ll cost;
        bool operator<(const Node s ) const{
                return cost > s.cost;
        }
};
void bfs(){
        priority_queue<Node > que;
        que.push((Node){1,0,0});
        dp[1][0]=0;
        while(!que.empty()){
                Node now = que.top();que.pop();
                ll s = now.s  , pos = now.pos , cost = now.cost;
                //cerr<<pos<<" "<<cost<<endl;
                if(cost > dp[s][pos]) continue;
                for(ll i=0;i<n;i++){
                        ll w = g[pos][i];
                        if(w + dp[s][pos] < dp[s|(1<<i)][i]){
                                dp[s|(1<<i)][i] = w + dp[s][pos];
                                que.push((Node){s|(1<<i), i ,w + dp[s][pos]});
                        }
                }
        }

}

int main(){
    #ifndef ONLINE_JUDGE
        //freopen("C:/OJ/in.txt","r",stdin);
    #endif
    ll T;scan(T);
    while(T--){
                MEM(g, 0x3f);
                MEM(dp,0x3f);
                scan2(n,m);
                for(ll i=0;i<m;i++){
                        ll u,v,w;scan3(u,v,w);
                        u--,v--;
                        //cerr<<u<<" "<<v<<" "<<w<<endl;
                        Min(g[u][v] , w);
                        Min(g[v][u] , w);
                }
                bfs();
                printf("%I64d\n", dp[(1<<n)-1][0]);
    }
        return 0;
}