#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("hardest.in");
ofstream out("hardest.out");
int T;
int INF=1<<28;
int m,n;
vector<int> G[201],C[201];
int DIJ()
{
	int f[201];
	bool l[201];
	int i;
	priority_queue <pair<int,int> > q;
	for(i=1;i<=n;i++)
	{
		f[i]=INF;
		l[i]=0;
	}
	q.push(make_pair(-f[1],1));
	f[1]=0;
	l[1]=1;
	
	while(!q.empty())
	{
		int u= q.top().second;
		q.pop();
		l[u]=0;
		for(i=0;i<G[u].size();i++)
		{
			int v=G[u][i];
			int c=C[u][i];
			if(f[v]>f[u]+c)
			{
				f[v]=f[u]+c;
				if(!l[v])
				{
					l[v]=1;
					q.push(make_pair(-f[v],v));
				}
			}
		}
	}
	return f[n];
}
int main()
{
	int i;
	int T,a,b,c,ans;
	in>>T;
	while(T--)
	{
		in>>n>>m;
		for(i=1;i<=200;i++)
		{
			G[i].clear();
			C[i].clear();
		}
		for(i=1;i<=m;i++)
		{
			in>>a>>b>>c;
			G[a].push_back(b);
			G[b].push_back(a);
			C[a].push_back(c);
			C[b].push_back(c);
		}
		ans=DIJ();
		if(ans==INF)out<<-1<<endl;
		else out<<ans<<endl;
	}
	return 0;
}