#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <iostream>
#include <cassert>
#include <bitset>
#include <ctime>

using namespace std;

typedef long long LL;
typedef double DB;
typedef pair<int, int> PII;
typedef vector<int> VI;

#define X first
#define Y second
#define pb push_back
#define bit(n) (1 << (n))

template<class T>
inline void chkmin(T &x, T y) {
    if (y < x) x = y;
}

template<class T>
inline void chkmax(T &x, T y) {
    if (x < y) x = y;
}

const int MN = 20;
const int oo = int(1e9);

struct Data {
    int x, s, d;
    Data(int x = 0, int s = 0, int d = 0) : x(x), s(s), d(d) {}
    bool operator<(const Data &D) const {
        return d > D.d;
    }
};

queue<Data> Q;
int n, m;
int chk[MN][1<<17], T;
int val[MN][1<<17];
int d[MN][MN];

int calc(int x, int s) {
    if (chk[x][s] == T) return val[x][s];
    if (s == 0) {
        if (x == 1) return 0;
        return oo;
    }
    chk[x][s] = T;
    int i, rlt = oo;
    for (i = 1; i <= n; i++) if (s & bit(i - 1)) {
        chkmin(rlt, d[i][x] + calc(i, s ^ bit(i - 1)));
    }
    return val[x][s] = rlt;
}

int main() {
    
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    
    int i, j, k, tn, w;
    
    for (scanf("%d", &tn); tn--; ) {
        scanf("%d%d", &n, &m);
        for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) d[i][j] = oo;
        for (i = 1; i <= n; i++) d[i][i] = 0;
        while (m--) {
            scanf("%d%d%d", &j, &k, &w);
            chkmin(d[j][k], w);
            chkmin(d[k][j], w);
        }
        for (k = 1; k <= n; k++)
            for (i = 1; i <= n; i++)
                for (j = 1; j <= n; j++)
                    chkmin(d[i][j], d[i][k] + d[k][j]);
        T++;
        printf("%d\n", calc(1, bit(n) - 1));
    }
    
    return 0;    
}