#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<cstdio>
#include <ctime>
#include<cassert>
#include <pthread.h>


using namespace std;

#define MEM(a,b) memset(a,(b),sizeof(a))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MP make_pair
#define pb push_back


#define maxn 10000
#define maxt 100
#define maxv 1000000
#define inf  1000000000

typedef long long  LL;

typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<pi> vpi;

int d[40][40];
int memo[1<<18][2],all,n;

inline int getbit(int mask,int x) { return mask&(1<<x) ? 1 : 0;}

/*Have to find the minimum weighted matching of the Radiant nodes in the new complete graph using
shortest paths as edge weights */

int solve(int mask,int x)
{
    int ret=inf;

    if(mask==all) return 0;
    if(memo[mask][x]!=-1 ) return memo[mask][x];
    for(int i=x;i<n;i+=2) if(!getbit(mask,i/2))
    {
        for(int j=i+2;j<n;j+=2) if(!getbit(mask,j/2))
        {
            int q=solve(mask|(1<<(i/2))|(1<<(j/2)),x);
            ret=MIN(ret,q+d[i][j]);
        }
        break;
    }

    return memo[mask][x]=ret;
}

int main()
{
   int i,j,k,T,m,cs=0;


   scanf("%d",&T);
   assert(T>=1 && T<=50);
   while(T--)
   {
      scanf("%d%d",&n,&m);
      assert(n%2==0);
      assert(n>=2 && n<=18);
      assert(m>=2*n-1 && m<= 2*n*(2*n-1)/2);
      all=(1<<n)-1;
      n*=2;

      for(i=0;i<n;i++)
        for(j=0;j<n;j++)  d[i][j]=inf;


      for(i=0;i<m;i++)
      {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        assert(c>=1 && c<=maxv);
        assert(a!=b && d[a][b]==inf);
        d[a][b]=d[b][a]=c;
      }

      // floyd warshal

      for(k=0;k<n;k++)
         for(i=0;i<n;i++)
             for(j=0;j<n;j++)
                d[i][j]=MIN(d[i][j],d[i][k]+d[k][j]);


      MEM(memo,-1);
      // solves for each case even numbered as Radiant and odd numbered as Radiant
      int ans=solve(0,0);
      ans=MIN(ans,solve(0,1));
      printf("%d\n",ans);
   }



	return 0;
}