#include<cstdio>

#include<algorithm>

#define rep(i,x,y) for (int i=x; i<y; i++)

using namespace std;

int cnt,M[1005][1005],H[5005][15][15],last[15],G[5005][15][2],F[5005];

struct node{

	int to,next,val;

}e[1000005];

void add(int a,int b,int c){

	e[++cnt].to=b;

	e[cnt].next=last[a];

	e[cnt].val=c;

	last[a]=cnt;

}

int main(){

	int T;

	scanf("%d",&T);

	while (T--){

		int n,m;

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

		cnt=0;

		for (int i=0; i<n; i++) last[i]=0;

		rep(i,0,n) rep(j,0,n) M[i][j]=1e9;

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

			int x,y,z;

			scanf("%d%d%d",&x,&y,&z);

			x--,y--;

			add(x,y,z);

			add(y,x,z);

			M[x][y]=min(M[x][y],z);

			M[y][x]=min(M[y][x],z);

		}

		int Max=(1<<n);

		rep(i,0,Max) rep(x,0,n) rep(y,0,n) H[i][x][y]=1e9;

		for (int i=0; i<n; i++) H[1<<i][i][i]=0;

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

			for (int S=0; S<n; S++)

				for (int T=0; T<n; T++)

					if (H[i][S][T]!=1e9){

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

							if (i&(1<<To)) continue;

							H[i|(1<<To)][S][To]=min(H[i|(1<<To)][S][To],H[i][S][T]+M[To][T]);

						}

					}

		rep(i,0,Max) rep(S,0,n) G[i][S][0]=G[i][S][1]=1e9;

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

			for (int S=0; S<n; S++)

				for (int j=last[S]; j; j=e[j].next){

					int T=e[j].to;

					if (i&(1<<T)){

						if (G[i][S][0]>=e[j].val){

							G[i][S][1]=G[i][S][0];

							G[i][S][0]=e[j].val;

						}

						else if (G[i][S][1]>e[j].val) G[i][S][1]=e[j].val;

					}

				}

		rep(i,0,Max) F[i]=1e9;

		for (int i=0; i<n; i++) F[1<<i]=0;

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

			for (int pre=(i-1)&i; pre; pre=(pre-1)&i){

				int now=i-pre;

				for (int S=0; S<n; S++)

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

						if (now&(1<<S) && now&(1<<T)){

							int Sum=H[now][S][T]+G[pre][S][0];

							if (Sum>=1e9) continue;

							if (S!=T) Sum+=G[pre][T][0];

							else Sum+=G[pre][T][1];

							F[i]=min(F[i],F[pre]+Sum);

						}

					}

			}

		if (F[Max-1]==1e9) printf("impossible\n");

		else printf("%d\n",F[Max-1]);

	}

	return 0;

}