#include <fstream>
using namespace std;
ifstream cin("hardest.in");
ofstream cout("hardest.out");
int n,m,f[201][201],t;
void init()
{
	int i,a,b,c,j;
	cin>>n>>m;
	for (i=1;i<=n-1;i++)
	{
		f[i][i]=0;
		for (j=i+1;j<=n;j++) {f[i][j]=99999;f[i][j]=99999;}
	}f[n][n]=0;
	for (i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		if (c<f[a][b]) {f[a][b]=c;f[b][a]=c;}
	}
}
int main()
{
	int i,j,k,l;
	cin>>t;
	for (l=1;l<=t;l++)
	{
		init();
		for (k=1;k<=n;k++)
			for (i=1;i<=n;i++)
				for (j=1;j<=n;j++)
				{
					if (f[i][k]!=99999&&f[k][j]!=99999&&i!=k&&i!=j&&k!=j)
					{
						if (f[i][k]+f[k][j]<f[i][j])
						{
							f[i][j]=f[i][k]+f[k][j];
							f[j][i]=f[i][k]+f[k][j];
						}
					}
				}
		if (f[1][n]!=99999) cout<<f[1][n]<<endl;else cout<<-1<<endl;
	}
	return 0;
}