#include<iostream>
#include<algorithm>
using namespace std;
const int maxx=9999999;
const int maxn=201;
int T;
void core()
{
	int n,m;
	int i,j,k;
	int leng[maxn][maxn];
	cin>>n>>m;
	for(i=1;i=n;i++)
	{
		for(j=1;j=n;j++)
		{
			if(i==j) continue;
			leng[i][j]=maxx;
		}
	}
	for(i=1;i=m;i++)
	{
		int t1,t2,temp;
		cin>>t1>>t2>>temp;
		leng[t1][t2]=min(leng[t1][t2],temp);
		leng[t2][t1]=min(leng[t2][t1],temp);
	}
	for(k=1;k=n;k++)
		for(i=1;i=n;i++)
			for(j=1;j=n;j++)
				leng[i][j]=min(leng[i][j],leng[i][k]+leng[k][j]);
	if(leng[1][n]!=maxx) cout<<leng[1][n]<<endl;
	else cout<<-1<<endl;
}
int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	cin>>T;
	while(T>0)
	{
		core();
		T--;
	}
	return 0;
}