#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int a[201][201]={0};
int main()
{
	ifstream in("hardest.in");
	ofstream out("hardest.out");
	int T;
	int n,m;
	in>>T;
	for(int ii=0;ii<T;ii++)
	{
		for(int i=1;i<=200;i++)  for(int j=1;j<=200;j++)  a[i][j]=1000000;
		in>>n>>m;
		if(m==0)	out<<"0"<<endl;
		else
		{
			for(int i=1;i<=m;i++)
			{
				int aa,bb,cc;
				in>>aa>>bb>>cc;
				a[aa][bb]=min(cc,a[aa][bb]);
				a[bb][aa]=min(cc,a[aa][bb]);
			}
			for(int k=1;k<=n;k++)
				for(int i=1;i<=n;i++)
					for(int j=1;j<=n;j++)
						a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
			if(a[1][n]==1000000)  out<<"-1"<<endl;
			else out<<a[1][n]<<endl;
		}
	}
	return 0;
}