#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
main(){
	freopen("hardest.in","r",stdin);freopen("hardest.out","w",stdout);
	short T,n,m,x,y,w,t=-1,i,j,k,maxx;
	int g[201][201],dis[201],maxm;
	bool vst[201];
	scanf("%hd",&T);
	while(++t<T){
		scanf("%hd%hd",&n,&m);
		memset(g,-1,sizeof(g));
		for(i=-1;++i<m;){
			scanf("%hd%hd%hd",&x,&y,&w);
			g[x][y]=g[y][x]=w;
		}
		memset(dis,-1,sizeof(dis));
		memset(vst,0,sizeof(vst));
		dis[1]=0;
		for(k=-1;++k<n;){
			maxm=0x7fffffff;
			for(i=0;++i<=n;)
				if(!vst[i]&&dis[i]>-1&&maxm>dis[i]){
					maxm=dis[i];
					maxx=i;
				}
			if(maxm==0x7fffffff){
				printf("-1\n");
				break;
			}
			else
				if(maxx==n){
					printf("%d",maxm);
					break;
				}
			vst[maxx]=1;
			for(i=0;++i<=n;)
				if(g[maxx][i]>-1)
					if(dis[i]>-1)
						dis[i]=min(dis[i],dis[maxx]+g[maxx][i]);
					else
						dis[i]=dis[maxx]+g[maxx][i];
		}
	}
}