#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long ll;

const int INF = 0x5f5f5f5f;

const int MAX = 1 << 17;

int mp[20][20];

int dp[MAX + 1][20];    // dp[s][v] 走过s点，现在在v点 dp[S][0]

int bit[1<<17];

int main()

{

    //freopen("in.txt", "r", stdin);

	for(int i = 0; i<(1<<16); i++) // bit[i] := i的二进制有多少个1

    {

        bit[i] = 0;

        for (int j = 0; j <= 16; j++)

            if (i & (1 << j))

              bit[i]++;

    }

    int t;

    int m, n;

    scanf("%d", &t);

    while (t--) {

        memset(mp, -1, sizeof mp);

        for (int i = 0; i < MAX; ++i)

            for (int j = 0; j < 16; ++j)

                dp[i][j] = INF;

        scanf("%d%d", &n, &m);

        int a, b, c;

        for (int i = 0; i < m; ++i) {

            scanf("%d%d%d", &a, &b, &c);

            if (mp[a - 1][b - 1] == -1 || mp[a - 1][b - 1] > c)

                mp[a - 1][b - 1] = mp[b - 1][a - 1] = c;

        }

        int maxn =  (1 << n) - 1;

		dp[1][0] = 0;

        for (int s = 1; s <= maxn; ++s) {

			for(int k = 0; k <= bit[s]; ++k) {

				for (int v = 0; v < n; ++v) {

					if (dp[s][v] != INF) {

						for (int u = 0; u < n; ++u) {

							if (mp[u][v] != -1) {

								if (dp[s | (1 << u)][u] > dp[s][v] + mp[u][v])

									dp[s | (1 << u)][u] = dp[s][v] + mp[u][v];

							}

						}

					}

				}

            }

        }

        printf("%d\n", dp[maxn][0]);

    }

    return 0;

}

/**

Input:

2

3 2

1 2 2

1 3 3

5 4

1 2 1

2 3 1

3 4 1

4 5 1

Output:

10

8

*/