如题，f[i][j][s]表示从i出发到j停止经过了s这个状态的点的最小代价，g[s]表示把s中的点包含到最终形成的强连通图所需最小代价。

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ll long long
using namespace std;
const int N=12;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const ll  INF=0x3f3f3f3f3f3f3f3f;

struct nod {
	int v,c;
};
int aqx,n,m;
ll f[N][N][(1<<N)+3],g[(1<<N)+3];
vector<nod> G[N+5];
vector<int> a[N][N];

int read() {
    int sss=0,www=1;
    char ccch=getchar();
    while(ccch<'0' || ccch>'9') { if(ccch=='-') www=-1; ccch=getchar(); }
    while(ccch>='0' && ccch<='9') sss=sss*10+ccch-'0',ccch=getchar();
    return sss*www;
}
void Add(ll &xcr, ll zzy) { xcr+=zzy,xcr=(xcr>mod?xcr-mod:xcr); }
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //ios::sync_with_stdio(false);
    aqx=read();
    while(aqx--)
    {
    	for(int i=0; i<n; i++) G[i].clear();
    	for(int i=0; i<n; i++)
    		for(int j=0; j<n; j++) a[i][j].clear();

    	n=read(),m=read();
    	for(int i=1,x,y,z; i<=m; i++)
    	{
    		x=read()-1,y=read()-1,z=read();
    		if(x==y) continue;
    		G[x].pb((nod){y,z});
    		G[y].pb((nod){x,z});
    		a[x][y].pb(z);
    		a[y][x].pb(z);
    	}
    	for(int i=0; i<n; i++)
    		for(int j=0; j<n; j++)
    			sort(a[i][j].begin(),a[i][j].end());

    	memset(f,0x3f,sizeof(f));
    	for(int i=0; i<n; i++) f[i][i][(1<<i)]=0;
    	for(int s=0,ed=(1<<n)-1; s<=ed; s++)
    		for(int i=0; i<n; i++)
    			if((s>>i)&1)
    				for(int j=0,k; j<n; j++)
    					if(((s>>j)&1) && f[i][j][s]<INF)
    						for(auto tk:G[j])
    						{
    							k=tk.v;
    							if(((s>>k)&1)) continue;
    							f[i][k][s|(1<<k)]=min(f[i][k][s|(1<<k)],f[i][j][s]+tk.c);
    						}

    	memset(g,0x3f,sizeof(g));
    	
    	for(int i=0; i<n; i++)
    		for(int j=0; j<n; j++)
    			if((int)a[i][j].size()>1)
    				g[(1<<i)|(1<<j)]=a[i][j][0]+a[i][j][1];
    	
    	for(int i=0; i<n; i++)
    		for(auto j:G[i])
    			for(int s=0,ed=(1<<n); s<ed; s++)
    				if(((s>>i)&1) && ((s>>j.v)&1) && (s^(1<<i)^(1<<j.v))>0)
    					g[s]=min(g[s],f[i][j.v][s]+j.c);
    	for(int s=0,ed=(1<<n)-1; s<=ed; s++)
    	{
    		int t=(ed^s);
    		for(int i=0; i<n; i++)
    			if((s>>i)&1)
    				for(int j=0; j<n; j++)
    					if((s>>j)&1)
    						for(int ss=t; ss; ss=(t&(ss-1)))
    							g[s^ss]=min(g[s^ss],g[s]+f[i][j][ss^(1<<i)^(1<<j)]);
    	}

    	if(g[(1<<n)-1]==INF) puts("impossible");
    	else printf("%lld\n", g[(1<<n)-1]);
    }
    
    return 0;
}