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