#include <cstring>
#include <cmath>
#include <cstdio>
#include <climits>
#include <ctime>
#include <cassert>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <bitset>
#include <utility>

#define all(x) (x).begin(), (x).end()
#define bit(x) (1 << (x))
#define cnt1(x) (__builtin_popcount(x))
#define LET(it,v) __typeof(v) it(v)
#define mset0(x) memset((x), 0, sizeof((x)))
#define mset1(x) memset((x), -1, sizeof((x)))
#define pb push_back
#define PQ priority_queue
#define REP(it,v) for(LET(it,v.begin());it!=v.end();it++)
#define sqr(x) ((x) * (x))
#define sz(x) ((int)(x.size()))
#define X first
#define Y second

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;

template <class T> inline void chkmin(T &a, T b) {
    if (b < a) a = b;
}
template <class T> inline void chkmax(T &a, T b) {
    if (a < b) a = b;
}

const int MX = 17;
const int INF = 100000000;

int rlt[bit(MX)][MX];
int con[MX][MX];

int main() {
    
    int n, m;
    int T, i, j, k;
    int u, v, w;
    
    for (scanf("%d", &T); T--; ) {
        scanf("%d%d", &n, &m);
        
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++) con[i][j] = INF;
        
        for (i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            chkmin(con[u][v], w);
            chkmin(con[v][u], w);
        }
        
        for (k = 1; k <= n; k++) {
            for (i = 1; i <= n; i++) {
                for (j = 1; j <= n; j++)
                    chkmin(con[i][j], con[i][k] + con[k][j]);
            }
        }
        for (i = 1; i <= n; i++) con[i][i] = 0;
        
        for (i = 0; i < bit(n); i++) {
            for (j = 0; j < n; j++) rlt[i][j] = INF;
        }
        rlt[1][0] = 0;
        
        for (int st = 1; st < n; st++) {
            for (i = 0; i < bit(n); i++) if (cnt1(i) == st) {
                for (k = 0; k < n; k++) if (bit(k) & i) {
                    for (j = 0; j < n; j++) {
                        chkmin(rlt[i + bit(j)][j], rlt[i][k] + con[k + 1][j + 1]);
                    }
                }
            }
        }
        
        int ans = INF;
        for (i = 0; i < n; i++) chkmin(ans, rlt[bit(n) - 1][i] + con[i + 1][1]);
        printf("%d\n", ans);
    }
    
    return 0;
}