#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("hardest.in");
ofstream fout("hardest.out");
int Map[201][201],T,N,M,MC[201];
bool flag[201];
class Node
{
public:
	int list[10000],head,tail;
	void init(int pos)
	{
		head=1;tail=2;
		list[1]=pos;
	}
}Q;
void Initialize()
{
int i,j;
	for(i=1;i<=200;i++)
	{
		for(j=1;j<=200;j++)
			if(i!=j)
				Map[i][j]=10000000;
		MC[i]=10000000;
	}
	MC[1]=0;
	fin>>N>>M;
	for(i=1;i<=M;i++)
	{
	int U,V,W;
		fin>>U>>V>>W;
		Map[U][V]=min(Map[U][V],W);
		Map[V][U]=min(Map[V][U],W);
	}
}
int main()
{
int i,j,k;
	fin>>T;
	for(int iT=1;iT<=T;iT++)
	{
		Initialize();
		
		for(k=1;k<=N;k++)
			for(i=1;i<=N;i++)
				for(j=1;j<=N;j++)
					if(Map[i][j]>Map[i][k]+Map[k][j])
						Map[i][j]=Map[i][k]+Map[k][j];
		Q.init(1);
		while(Q.head<Q.tail)
		{
			for(int p=1;p<=N;p++)
				if(Map[Q.list[Q.head]][p]!=10000000)
					if(MC[p]>MC[Q.list[Q.head]]+Map[Q.list[Q.head]][p])
					{
						MC[p]=MC[Q.list[Q.head]]+Map[Q.list[Q.head]][p];
						if(flag[p]==false)
							Q.list[Q.tail++]=p;
						flag[p]=true;
					}
			Q.head++;
		}
		if(MC[N]==10000000)
			fout<<-1<<endl;
		else
			fout<<MC[N]<<endl;
	}
	
	fin.close();
	fout.close();
	return 0;
}