#include<bits/stdc++.h>
using namespace std;
#define ll long long

namespace acac
{
	
	
	inline int read()
	{
		char ch=getchar();
		int ans=0;
		while(ch<'0'||ch>'9')
		{
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')
		{
			ans=ans*10+ch-'0';
			ch=getchar();
		}
		return ans;
	}

	int n,m;
	
	int dp[5010][20][20][3],f[5010],e[20][20][3];
	
	int main()
	{
		int T=read();
		while(T--)
		{
			n=read(),m=read();
			memset(dp,0x2f,sizeof(dp));
			memset(f,0x2f,sizeof(f));
			memset(e,0x2f,sizeof(e));
			for(int i=1;i<=m;i++)
			{
				int a=read(),b=read(),v=read();
				if(v<e[a][b][0])e[a][b][1]=e[a][b][0],e[a][b][0]=v;
				else if(v<e[a][b][1])e[a][b][1]=v;
				if(v<e[b][a][0])e[b][a][1]=e[b][a][0],e[b][a][0]=v;
				else if(v<e[b][a][1])e[b][a][1]=v;
			}
			for(int i=1;i<=n;i++)
			{
				f[(1<<(i-1))]=0;
			}
			int N=(1<<n)-1;
			for(int i=1;i<=N;i++)
			{
				for(int u=1;u<=n;u++)
				{
					if(!(i&(1<<(u-1))))continue;
					for(int v=1;v<=n;v++)
					{
						if(!(i&(1<<(v-1))))continue;
						f[i]=min(f[i],dp[i][u][v][1]+e[u][v][0]);
					}
				}
				if(f[i]<0x2f2f2f2f)
				{
					for(int u=1;u<=n;u++)
					{
						if(!(i&(1<<(u-1))))continue;
						for(int v=1;v<=n;v++)
						{
							if(!(i&(1<<(v-1))))continue;
							f[i|(1<<(u-1))]=min(f[i|(1<<(u-1))],f[i]+e[u][v][0]+e[u][v][1]);
						}
					}
					for(int u=1;u<=n;u++)
					{
						if(!(i&(1<<(u-1))))continue;
						for(int v=1;v<=n;v++)
						{
							if(!(i&(1<<(v-1))))continue;
							for(int l=1;l<=n;l++)
							{
								if(i&(1<<(l-1)))continue;
								
								dp[i|(1<<(l-1))][l][v][0]=min(dp[i|(1<<(l-1))][l][v][0],f[i]+e[u][l][0]);
								if(u!=v)f[i|(1<<(l-1))]=min(f[i|(1<<(l-1))],f[i]+e[u][l][0]+e[l][v][0]);
							}
						}
					}
				}
				for(int u=1;u<=n;u++)
				{
					if(!(i&(1<<(u-1))))continue;
					for(int v=1;v<=n;v++)
					{
						if(!(i&(1<<(v-1)))||min(dp[i][u][v][0],dp[i][u][v][1])>=0x2f2f2f2f)continue;
						for(int l=1;l<=n;l++)
						{
							if(i&(1<<(l-1)))continue;
							
							dp[i|(1<<(l-1))][l][v][1]=min(dp[i|(1<<(l-1))][l][v][1],min(dp[i][u][v][0],dp[i][u][v][1])+e[u][l][0]);
						}
					}
				}
			}
			if(f[N]>=0x2f2f2f2f)cout<<"impossible\n";
			else cout<<f[N]<<'\n';
		} 

		return 0;
	}
}

int main()
{
	acac::main();
	return 0;
}

rt,最后判的无解QWQ