这道题。。。神题。
首先看到数据范围，一眼状压 dp 。然后？ 没了。
理性分析，这里说断掉任意一条边图依然连通，即整个图构成一个边双（而不是点双）。
之前用 fire （机房里的随机算法总称）之所以过不掉大概是我想错性质了（边双的条件直接变成 任意点的度大于2），
再打一遍 fire 不知道能不能过（可能关于判边双会十分麻烦，且复杂度较高）。
在这里我们考虑一个边双加上一条链（链的两端都在边双的集合里面），然后这个图依旧是边双。
那么在这里，一个点既是边双又是链，只不过要特判点 这一特殊情况。
然后我们可以处理出每一条链的最短长度，再进行边双最优解转移。
//by Judge
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=1e9+;
const int M=(<<)+;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline void cmin(int& a,int b){if(a>b)a=b;}
char buf[<<],*p1=buf,*p2=buf;
inline int read(){ int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} int n,m,pat,msk,head[],log[M],h1[][M],h2[][M],g[][][M],f[M];
struct edge{ int to,val,next; }e[];
inline void add(int x,int y,int z){
e[++pat]={y,z,head[x]},head[x]=pat;
e[++pat]={x,z,head[y]},head[y]=pat;
}
#define lowbit(x) (x&-x)
int main(){ int T=read();
while(T--){ n=read(),m=read(),
msk=(<<n)-,pat=;
memset(head,,sizeof(head));
for(int i=;i<n;++i) log[<<i]=i;
for(int i=,a,b,c;i<m;++i)
a=read()-,b=read()-,
c=read(),add(a,b,c);
memset(h1,0x0f,sizeof(h1)),
memset(h2,0x0f,sizeof(h2)),
memset(g,0x0f,sizeof(g));
memset(f,0x0f,sizeof(f));
#define v e[i].to
for(int i,S=,a;S<=msk;++S){
for(int ta=msk^S;ta;ta-=lowbit(ta)){
for(a=log[lowbit(ta)],i=head[a];i;i=e[i].next) if((S>>v)&){
if(e[i].val<h1[a][S]) h2[a][S]=h1[a][S],h1[a][S]=e[i].val;
else cmin(h2[a][S],e[i].val);
}
}
}
for(int i=;i<n;++i) g[i][i][<<i]=f[<<i]=;
for(int S=;S<=msk;++S) for(int ta=S,a;ta;ta-=lowbit(ta))
for(int tb=S,b;tb;tb-=lowbit(tb)){
a=log[lowbit(ta)],b=log[lowbit(tb)]; if(a==b) continue;
for(int i=head[b];i;i=e[i].next) if((S>>v)&)
cmin(g[a][b][S],g[a][v][S^(<<b)]+e[i].val);
}
for(int S=,a,b;S<=msk;++S) if(S^lowbit(S)){
for(int T=(S-)&S;T;T=(T-)&S) for(int ta=T;ta;ta-=lowbit(ta))
for(int tb=T;tb;tb-=lowbit(tb)){ a=log[lowbit(ta)],b=log[lowbit(tb)];
if(a==b) cmin(f[S],f[S^T]+g[a][b][T]+h1[a][S^T]+h2[a][S^T]);
else cmin(f[S],f[S^T]+g[a][b][T]+h1[a][S^T]+h1[b][S^T]);
}
}
if(f[msk]>=f[]) puts("impossible");
else printf("%d\n",f[msk]);
} return ;
}