#pragma comment(linker, "/STACK:10240000")
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define X                   first
#define Y                   second
#define pb                  push_back
#define mp                  make_pair
#define all(a)              (a).begin(), (a).end()
#define fillchar(a, x)      memset(a, x, sizeof(a))
#define fillarray(a, b)     memcpy(a, b, sizeof(a))

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}

const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double EPS = 1e-12;

/* -------------------------------------------------------------------------------- */

const int maxn = 16;

int n;
int e[maxn][maxn], d[maxn][1 << maxn], vis[maxn][1 << maxn];

void add(int u, int v, int w) {
    u --;
    v --;
    umin(e[u][v], w);
}

bool relax(pii u, pii v, int w) {
    if (d[v.X][v.Y] > d[u.X][u.Y] + w) {
        d[v.X][v.Y] = d[u.X][u.Y] + w;
        return true;
    }
    return false;
}

void work() {
    fillchar(vis, 0);
    fillchar(d, 0x3f);
    queue<pii> Q;
    Q.push(mp(0, 1));
    d[0][1] = 0;
    vis[0][1] = true;
    while (!Q.empty()) {
        pii H = Q.front(); Q.pop();
        vis[H.X][H.Y] = false;
        for (int i = 0; i < n; i ++) {
            if (e[H.X][i] < INF) {
                pii P = mp(i, H.Y | (1 << i));
                if (relax(H, P, e[H.X][i]) && !vis[P.X][P.Y]) {
                    vis[P.X][P.Y] = true;
                    Q.push(P);
                }
            }
        }
    }
    cout << d[0][(1 << n) - 1] << endl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int T, u, v, w, m;
    cin >> T;
    while (T --) {
        cin >> n >> m;
        fillchar(e, 0x3f);
        for (int i = 0; i < m; i ++) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }
        work();
    }
    return 0;
}