#include<stdio.h>
int T,n,m,v[20010],w[20010],first[201],next[20010],dis[201],use[201],len;
int h,t,q[201];
void add(int uu,int vv,int ww);
int spfa();
int main()
{
	FILE *in=fopen("hardest.in","r");
	FILE *out=fopen("hardest.out","w");
	int i,k,x,y,z;
	fscanf(in,"%d",&T);
	for(k=1;k<=T;k++)
	{
		fscanf(in,"%d %d",&n,&m);
		for(i=1;i<=n;i++)
			first[i]=0;
		for(i=1,len=0;i<=n;i++)
		{
			fscanf(in,"%d %d %d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
			}
		spfa();
		if(dis[n]==0x7ffffff)
			fprintf(out,"-1\n");
		else 
			fprintf(out,"%d\n",dis[n]);
		}
	return 0;
	}
void add(int uu,int vv,int ww)
{
	len++;
	w[len]=ww;
	v[len]=vv;
	next[len]=first[uu];
	first[uu]=len;
	}
int spfa()
{
	int i,x;
	for(i=1;i<=n;i++)
		dis[i]=0x7ffffff;
	dis[1]=0;
	h=1;
	t=2;
	q[h]=1;
	use[1]=1;
	while(h!=t)
	{
		i=q[h];
		x=first[i];
		while(x)
		{
			if(dis[v[x]]>dis[i]+w[x])
			{
				dis[v[x]]=dis[i]+w[x];
				if(use[v[x]]==0)
				{
					use[v[x]]=1;
					q[t]=v[x];
					t=t%n+1;
					}
				}
			x=next[x];
			}
		use[i]=0;
		h=h%n+1;
		}
	return 0;
	}