#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int t,n,m,a,b,tmp,num,number,j;
vector<int>con[205];
vector<int>val[205];
bool used[205]={0};
int maxn[205]={0};
queue<int>q;
void spfa();
int main()
{
	freopen ("hardest.in","r",stdin);
	freopen ("hardest.out","w",stdout);
	cin>>t;
	for (int o=0;o<t;o++)
	{
		cin>>n>>m;
		for (int p=1;p<=n;p++)
		{
			con[p].clear();
			val[p].clear();
			used[p]=0;
			maxn[p]=99999999;
		}
		for (int i=0;i<m;i++)
		{
			cin>>a>>b>>tmp;
			con[a].push_back(b);
			con[b].push_back(a);
			val[a].push_back(tmp);
			val[b].push_back(tmp);
		}
		while (!q.empty())
			q.pop();
		spfa();
		if (maxn[n]==99999999)
			cout<<-1<<endl;
		else
			cout<<maxn[n]<<endl;
	}
	return 0;
}

void spfa()
{
	q.push(1);
	maxn[1]=0;
	used[1]=1;
	while (!q.empty())
	{
		num=q.front();
		number=maxn[num];
		for (int i=0;i<con[num].size();i++)
		{
			j=con[num][i];
			if (!used[j]&&maxn[j]>number+val[num][i])
			{
				maxn[j]=number+val[num][i];
				q.push(j);
				used[j]=1;
			}
			if (used[j]&&maxn[j]>number+val[num][i])
			{
				maxn[j]=number+val[num][i];
			}
		}
		used[num]=0;
		q.pop();
	}
}