#include<cmath>
#include<cstdio>
int  q;
int  n,m;
int  a,b;
int  i,j;
int  dist[40000],c[40000];
int  f[1000000],top,tai;
int  L[40000],W[40000],T[40000],D[40000],t;
int  main ( )
{
	freopen ("hardest.in" ,"r",stdin );
	freopen ("hardest.out","w",stdout);
	scanf("%d",&q);
	while (q--)
	{
		scanf("%d%d",&n,&m);
		for (i=1; i<=n; i++) W[i]=0;
		for (i=1; i<=m; i++)
		{
			scanf("%d%d%d",&a,&b,&j);
			L[++t]=W[a]; W[a]=t; T[t]=b; D[t]=j;
			L[++t]=W[b]; W[b]=t; T[t]=a; D[t]=j;
		}
		for (i=1; i< n; i++) dist[i]=3000000; 
		dist [n]=0;
		f[tai=1]=n;
		for (top=1; top<=tai; c[f[top++]]=0)
		{
			for (i=W[f[top]]; i; i=L[i])
			if (dist[f[top]]+D[i]<dist[T[i]])
			{
				dist[T[i]]=dist[f[top]]+D[i];
				if (!c[D[i]]) f[++tai]=D[i] ,c[D[i]]=1;
			}
		}
		if (dist[1]==3000000) printf("-1\n");
		else printf("%d\n",dist[1]);
	}
}