#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
ifstream fin("hardest.in");
ofstream fout("hardest.out");

int T,n,m,g[205][205]={0};

int MIN(int a,int b){
    if(a<b) return a;return b;
    }

int main()
{
    fin>>T;
    
    while(T>0)
    {
      T--;
      fin>>n>>m;
      
      if(n==1) {fout<<0<<endl;continue;}
      
      for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
      g[i][j]=1000000000;
      
      for(int i=1;i<=m;++i)
      {
        int u,v,w;
        fin>>u>>v>>w;
        g[u][v]=g[v][u]=MIN(g[u][v],w);
              }
      
      for(int k=1;k<=n;++k)
      for(int i=1;i<=n;++i)
      if(i!=k)
      for(int j=1;j<=n;++j)
      if(i!=j&&j!=k)
      g[i][j]=g[j][i]=MIN(g[i][j],g[i][k]+g[k][j]);
      
      if(g[1][n]==1000000000) {fout<<-1<<endl;continue;}
      fout<<g[1][n]<<endl;        
              }
  //  system("pause");
    return 0;    

    }