#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<iostream>
#define PB push_back
#define POB pop_back
#define PII pair<int, int>
#define PDD pair<double, double>
#define rep(i, a, b) for(int i = a ; i < b ; i++)
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int maxn = 17;
const int inf = 0x3f3f3f3f;
int dp[1 << maxn][maxn];
int d[20][20];
int n, m;
void slove() {
    for(int S = 0 ; S < (1 << n) ; S++)
        fill(dp[S], dp[S] + n, inf);
    dp[(1 << n) - 1][0] = 0;
    for(int S = (1 << n) - 2 ; 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] + d[v][u]);
        }
    }
    printf("%d\n", dp[0][0]);
}
int main()
{
    int T; scanf("%d", &T);
    while(T--) {
        memset(d, 0x3f, sizeof d);
        int u, v, w;
        scanf("%d%d", &n, &m);
        for(int i = 0 ; i < m ; i++)
            scanf("%d%d%d", &u, &v, &w), d[u - 1][v - 1] = d[v - 1][u - 1] = min(d[u - 1][v - 1], w);
        for(int i = 0 ; i < n ; i++) d[i][i] = 0;
        for(int k = 0 ; k < n ; k++)
            for(int i = 0 ; i < n ; i++)
                for(int j = 0 ; j < n ; j++)
                    if(d[i][k] != 0x3f3f3f3f && d[k][j] != 0x3f3f3f3f)
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        slove();
    }
    return 0;
}