#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
	int s,nex;
}a[1100];
struct edge{
	int y,v,nex;
}e[800000];
int T,n,m,i,j,k,x,y,v,p;
bool vis[1010];
int f[1010][1010];
int aa[1010];
int dis[1010];
int queue[10000];
int DP[1010];
void add(int x,int y,int v){
	p++;
	a[x].s++;
	e[p].y=y;
	e[p].v=v;
	e[p].nex=a[x].nex;
	a[x].nex=p;
}
void SPFA(int s){
	int t;
	int tmp;
	memset(vis,true,sizeof(vis));
	memset(dis,0x7F,sizeof(dis));
	memset(queue,0,sizeof(queue));
	vis[s]=false;
	dis[s]=0;
	int head=0;
	int tail=1;
	queue[tail]=s;
	while (head<=tail){
		head++;
		tmp=queue[head];
		vis[tmp]=true;
		t=a[tmp].nex;
		for (int i=1;i<=a[tmp].s;i++){
			if (dis[tmp]+e[t].v<dis[e[t].y]){
				dis[e[t].y]=dis[tmp]+e[t].v;
				if (vis[e[t].y]){
					vis[e[t].y]=false;
					queue[++tail]=e[t].y;
				}
			}
			t=e[t].nex;
		}
	}
	if (dis[n]==dis[0]) dis[n]=-1;
	printf("%d\n",dis[n]);
}

int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	scanf("%d",&T);
	for (int II=1;II<=T;II++)
	{
		p=0;
		memset(a,0,sizeof(a));
		memset(e,0,sizeof(e));
		scanf("%d%d",&n,&m);
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&v);
			add(x,y,v);
			add(y,x,v);
		}
		SPFA(1);
	}
	return 0;
}