#include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<vector>

 #include<queue>

 using namespace std;

 const int N=;

 int first[N],to[N*],nex[N*],edge[N*],tot=,d[N],v[N];

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

     to[++tot]=b,edge[tot]=c,nex[tot]=first[a],first[a]=tot;

 }

 priority_queue<pair<int ,int > >q;

 void dij(int k){

     memset(d,0x3f,sizeof(d));

     memset(v,,sizeof(v));

     q.push(make_pair(,k));

     d[k]=;

     while(q.size()){

         int x=q.top().second;

         q.pop();

         if(v[x]) continue;

         v[x]=;

         for(int i=first[x];i;i=nex[i]){

             int y=to[i],z=edge[i];

             if(d[y]>d[x]+z){

                 d[y]=d[x]+z;

                 q.push(make_pair(-d[y],y));

             }

         }

     }

 }

 void init(){

     tot=;

     memset(first,,sizeof(first));

     memset(nex,,sizeof(nex));

     memset(to,,sizeof(to));

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         int n,m;

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

         init();

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

             int x,y,z;

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

             add(x,y,z);

             add(y,x,z);

         }

         int ans=;

         for(int i=first[];i;i=nex[i]){

             int z=edge[i],y=to[i];

             edge[i]=edge[i^]=;

             dij();

             ans=min(ans,d[y]+z);

             edge[i]=edge[i^]=z;

         }

         if(ans==) {puts("-1");continue;}

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

     }

 }