#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>

using namespace std;

const int oo = 100000000;
struct node
{
    int pos , num;
    node() {}
    node(int x , int y ):pos(x) , num(y){}
};
queue<node>que;
int t , n , m , dp[100000][20] , edge[30][30];
bool vis[100000][20];

int main()
{
    scanf("%d",&t);
    while( t-- )
    {
        scanf( "%d%d", &n, &m );
        for( int i = 1 ; i <= n; i++ )
            for( int j = 1 ; j <= n ; j++ )
                edge[i][j] = oo;
        while( m-- )
        {
            int x , y , z;
            scanf( "%d%d%d" , &x , &y , &z );
            edge[x][y] = edge[y][x] = min( edge[x][y] , z );
        }
        for( int i = 1 ; i < (1<<n) ; i++ )
            for( int j = 1 ; j <= n ; j++ )
            {
                dp[i][j] = oo;
                vis[i][j] = 0;
            }
        que.push( node( 1 , 1 ) );
        vis[1][1] = 1;
        dp[1][1] = 0;
        while( !que.empty() )
        {
            node cur = que.front();
            que.pop();
            for( int i = 1 ; i <= n ; i++ )
                if( dp[cur.pos|(1<<(i-1))][i] > dp[cur.pos][cur.num]+edge[cur.num][i] )
                {
                    dp[cur.pos|(1<<(i-1))][i] = dp[cur.pos][cur.num]+edge[cur.num][i];
                    if( !vis[cur.pos|(1<<(i-1))][i] )
                        que.push( node( cur.pos|(1<<(i-1)) , i ) );
                    vis[cur.pos|(1<<(i-1))][i] = 1;
                }
            vis[cur.pos][cur.num] = 0;
        }
        printf( "%d\n" , dp[(1<<n)-1][1] );
    }
    return 0;
}