#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=211;
const int INF=(~0u>>2)-4;
int F[MAXN][MAXN],N,M,T;

inline void clear()
{
	scanf("%d %d\n",&N,&M);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			if(i!=j) F[i][j]=INF;
	int x,y,z;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d %d\n",&x,&y,&z);
		if(z<F[x][y]) {F[x][y]=z,F[y][x]=z;}
	}
}

inline void floyd()
{
	for(int k=1;k<=N;k++)
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
				if(F[i][k]+F[k][j]<F[i][j])
					F[i][j]=F[i][k]+F[k][j];
	if(F[1][N]!=INF) printf("%d\n",F[1][N]);
	else printf("-1\n");
}

int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	scanf("%d\n",&T);
	for(int i=1;i<=T;i++)
	{
		clear();floyd();
	}
	return 0;
}