#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iomanip>

using namespace std;

#define repu(i, a, b) for (int i = (a); i < (b); ++i)
#define repd(i, a, b) for (int i = (a); i > (b); --i)
#define mem(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define uni(a) a.erase(unique(all(a)), a.end())
#define count_bits(x) __builtin_popcount(x)
#define count_bitsll(x) __builtin_popcountll(x)

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) {return (a < b) ? a : b;}
template<class T, class U> inline T tmax(T a, U b) {return (a > b) ? a : b;}
template<class T, class U> inline void amax(T &a, U b) {if (b > a) a = b;}
template<class T, class U> inline void amin(T &a, U b) {if (b < a) a = b;}
template<class T> inline T tabs(T a) {return (a > 0) ? a : -a;}
template<class T> T gcd(T a, T b) {while (b != 0) {T c = a; a = b; b = c % b;} return a;}

const int N = 16, INF = 1e5;
int n, d[N][N], dp[1 << N][N];

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    
    int ntest, m, u, v, w;
    
    cin >> ntest;
    while (ntest--) {
        cin >> n >> m;
        repu(i, 0, N) {
            repu(j, 0, N) d[i][j] = INF;
            d[i][i] = 0;
        }
        repu(i, 0, m) {
            cin >> u >> v >> w;
            u--; v--;
            amin(d[u][v], w);
            amin(d[v][u], w);
        }
        
        repu(k, 0, n) repu(i, 0, n) repu(j, 0, n) {
            amin(d[i][j], d[i][k] + d[k][j]);
        }
        
        repu(i, 0, (1 << n)) fill(dp[i], dp[i] + N, INF);
        
        dp[(1 << n) - 1][0] = 0;
        
        for (int s = (1 << n) - 2; s >= 0; --s) {
            for (v = 0; v < n; ++v) {
                for (u = 0; u < n; ++u) {
                    if (!(s >> u & 1)) {
                        amin(dp[s][v], dp[s | 1 << u][u] + d[v][u]);
                    }
                }
            }
        }
        
        printf("%d\n", dp[0][0]);
    }
    
    return 0;
}