#include<iostream>
#include<fstream>
using namespace std;
int a[201][201];
int m,n;
int zx(int a,int b){
	if(a<b) return a;
	else return b;}
void f(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				a[i][j]=zx(a[i][j],a[i][k]+a[k][j]);
		    }
		}
	}
}
int main(){
	ifstream fin("hardest.in");
	ofstream fout("hardest.out");
	int x,y,z,b;
	fin>>b;
	for(int l=0;l<b;l++){
		fin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				a[i][j]=10000000;
			}
		}
		for(int i=0;i<m;i++){
			fin>>x>>y>>z;
			a[x][y]=z;
			a[y][x]=z;
		}
		f();
		if(a[1][n]==10000000) fout<<-1<<endl;
		else fout<<a[1][n]<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}