#include<cstdio>

 #define F(i,a,b) for(int i=a;i<=b;i++)

 inline void up(int &x,int y){if(x>y)x=y;}

 int dp[<<][],g[][],inf=<<,n,m,t,u,v,c,end,ans;

 int main(){

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&m),end=(<<n)-,ans=inf;

         F(i,,n)F(j,,n)g[i][j]=(i==j?:inf);

         F(i,,m)scanf("%d%d%d",&u,&v,&c),up(g[u][v],c),up(g[v][u],c);

         F(k,,n)F(i,,n)F(j,,n)up(g[i][j],g[i][k]+g[k][j]);//Floyd

         F(i,,end)F(j,,n)dp[i][j]=inf;

         dp[][]=;

         F(i,,end)F(j,,n)if(dp[i][j]!=inf)F(k,,n)

         if(k==j||i&<<k-)continue;

         else up(dp[i|<<k-][k],dp[i][j]+g[j][k]);

         F(i,,n)up(ans,dp[end][i]+g[i][]);

         printf("%d\n",ans);

     }

     return ;

 }