#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f

struct City
{
    int vis, x;
};

int w[20][20], f[66000][20], n, m;
bool v[66000][20];
queue<City> q;

void Bfs()
{
    f[1][1] = 0;
    City a, b;
    a.vis = 1; a.x = 1; q.push(a); v[1][1] = 1;
    while (!q.empty())
    {
        a = q.front(); q.pop(); v[a.vis][a.x] = 0;
        for (int i = 1; i <= n; i++)
        if (w[a.x][i] + f[a.vis][a.x] < f[a.vis|(1<<i-1)][i])
        {
            b.vis = a.vis | (1 << i-1); b.x = i;
            f[b.vis][b.x] = w[a.x][b.x] + f[a.vis][a.x];
            if (!v[b.vis][b.x])
                v[b.vis][b.x] = 1;
            q.push(b);
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(f, INF, sizeof(f));
        memset(v, 0, sizeof(v));
        memset(w, INF, sizeof(w));
        while (!q.empty()) q.pop();
        scanf("%d%d", &n, &m);
        while (m--)
        {
            int A, B, C;
            scanf("%d%d%d", &A, &B, &C);
            if (C < w[A][B])
                w[A][B] = w[B][A] = C;
        }
        Bfs();
        int ans = f[(1<<n)-1][1];
        /*for (int i = 1; i <= n; i++)
        if (f[(1<<n)-1][i] < ans) ans = f[(1<<n)-1][i];
        ans <<= 1;*/
        printf("%d\n", ans);
    }
    return 0;
}