#include<fstream>
#include<queue>
#include<set>
using namespace std;
int map[201][201];
struct yu
{
	int v;
	int x;
};
yu tmp;
int n,m;
int spfa()
{
	int f[201];
	int i;
	f[1]=0;
	for(i=2;i<=n;i++)
		f[i]=~0u>>1;
	queue<yu> dq;
	tmp.x=1;
	tmp.v=0;
	dq.push(tmp);
	while(dq.size())
	{
		for(i=1;i<=n;i++)
		{
			tmp=dq.front();
			if(map[tmp.x][i])
			{
				if(f[i]>map[tmp.x][i]+tmp.v)
				{
					tmp.v=map[tmp.x][i]+tmp.v;
					tmp.x=i;
					f[i]=tmp.v;
					//if(i==n)
						//return f[i];
					if(i!=n)
						dq.push(tmp);
				}
			}
		}
		dq.pop();
	}
	if(f[n]==~0u>>1)
		return -1;
	else
		return f[n];
}
int min(int a,int b)
{
	if(a>b)
		return b;
	else
		return a;
}
int main(void)
{
	ifstream fin("hardest.in");
	ofstream fout("hardest.out");
	int t;
	fin>>t;
	for(;t;t--)
	{
		fin>>n>>m;
		int i,j,k;
		int p;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=0;
		for(p=0;p<m;p++)
		{
			fin>>i>>j>>k;
			if(map[i][j])
				k=min(map[i][j],k);
			map[i][j]=k;
			map[j][i]=k;
		}
		fout<<spfa()<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}