#include <iostream>
#include <cstdio>
using namespace std;

struct Line{
	int x,l;
	Line *next;
	Line(int a,int b,Line *c):
		x(a), l(b), next(c) {}
}* G[201];

int queue[20000],dist[201],n;
bool inque[201];
int spfa(){
	memset(dist,0x3f,sizeof(dist));
	memset(inque,0,sizeof(inque));
	queue[0]=1; dist[1]=0; 
	int h=0, t=1, x, k;
	while(h<t){
		x=queue[h++]; inque[x]=false;
		for(Line *p=G[x];p;p=p->next){
			if((k=dist[x]+p->l)<dist[p->x]){
				dist[p->x]=k;
				if(!inque[p->x]){
					inque[p->x]=true;
					queue[t++]=p->x;
				} 
			}
		}
	}
	return (dist[n]==0x3f3f3f3f?-1:dist[n]);
}

void solve(){
	int a,b,c,m;
	scanf("%d%d",&n,&m);
	while(m--){
		scanf("%d%d%d",&a,&b,&c);
		G[a]=new Line(b,c,G[a]);
		G[b]=new Line(a,c,G[b]);
	}
	printf("%d\n",spfa());
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--)solve();
}