#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 1<<29
#define N 300
using namespace std;
int g[N][N],n,m,T;
int dis[N];
bool inque[N];
int spfa()
{
	for(int i=1;i<=n;i++)
	  dis[i]=MAX;
	memset(inque,false,sizeof(inque));
	dis[1]=0;
	queue<int> que;
	inque[1]=true;
	que.push(1);
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		inque[u]=false;
		for(int i=1;i<=n;i++)
		{
			if(g[u][i] && dis[u]+g[u][i]<dis[i])
			{
				dis[i]=dis[u]+g[u][i];
				if(!inque[i])
				{
					que.push(i);
					inque[i]=true;
				}
			}
		}
	}
	if(dis[n]==MAX)
	  return -1;
	return dis[n];
}
int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		int u,v,k;
		memset(g,0,sizeof(g));
		for(int i=1;i<=m;i++)
		{
			cin>>u>>v>>k;
			if(g[u][v]==0 || (g[u][v]!=0 && g[u][v]>k))
			{
			   g[u][v]=k;
			   g[v][u]=k;
		    }
		}
		cout<<spfa()<<endl;
	}
	return 0;
}