/*
COGS
P1254
*/
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<assert.h>
#ifdef TEST
#define MAXN 10010
#else
#define MAXN 10010
#endif
#define INF 10000000
FILE *fin,*fout;
int T,n,m;
int head[MAXN],u[MAXN*4],v[MAXN*4],w[MAXN*4],next[MAXN*4];
int inq[MAXN],queue[MAXN*1000],front,rear; //数组模拟队列
int d[MAXN];//距离
long long int ans;//答案
void read_graph()
{
	fscanf(fin,"%d %d",&n,&m);
	int i;
	memset(head,-1,sizeof(head));
	for(i=0;i<m;i++)
	{
		fscanf(fin,"%d %d %d",&u[i],&v[i],&w[i]);
		next[i]=head[u[i]],head[u[i]]=i;
		u[i+m]=v[i],v[i+m]=u[i],w[i+m]=w[i];
		next[i+m]=head[u[i+m]],head[u[i+m]]=i+m;
	}
}


void SPFA()
{
	int i;
	ans=0;front=rear=0;
	memset(inq,0,sizeof(inq));
	for(i=1;i<=n;i++)  d[i]=INF;
	d[1]=0;
	queue[rear++]=1;
	while(front<rear)
	{
		int x=queue[front++];
		inq[x]=0;
		int e;
		for(e=head[x];e!=-1;e=next[e])
			if(d[v[e]]>d[x]+w[e])
			{
				d[v[e]]=d[x]+w[e];
				if(!inq[v[e]])
				{
					inq[v[e]]=1;
					queue[rear++]=v[e];
				}
			}
	}
	if(d[n]==INF)
		ans=-1;
	else
		ans=d[n];
}
int main()
{
	fin=fopen("hardest.in","r");fout=fopen("hardest.out","w");
	assert(fin&&fout);
	fscanf(fin,"%d",&T);
	while(T)
	{
		read_graph();
		SPFA();
		fprintf(fout,"%lld\n",ans);
		T--;
	}
	#ifdef HIGH
	fprintf(fout,"%.2lf",(double)clock()/CLOCKS_PER_SEC);
	#endif
	fclose(fin);fclose(fout);
	return 0;
}