#include<fstream>
#include<vector>
#include<deque>
using namespace std;
int main()
{
	ifstream fi("hardest.in");
	ofstream fo("hardest.out");
	int t;
	fi>>t;
	for(;t>0;t--)
	{
		bool f[202]={0};
		vector<short int>r[202],q[202];
		deque<int>d;
		int n,m,a,b,c,end[202]={0};
		fi>>n>>m;
		for(int i=1;i<=n;i++)
		{
			r[i].push_back(0);
			q[i].push_back(0);
			end[i]=99999999;
		}
		for(int i=1;i<=m;i++)
		{
			fi>>a>>b>>c;
			r[a].push_back(b);
			q[a].push_back(c);
			r[b].push_back(a);
			q[b].push_back(c);
			r[a][0]++;
			r[b][0]++;
		}
		d.push_back(1);
		f[1]=1;
		end[1]=0;
		while(!d.empty())
		{
			int t=d.front();
			d.pop_front();
			f[t]=0;
			for(int i=1;i<=r[t][0];i++)
			{
				if(end[t]+q[t][i]<end[r[t][i]])
				{
					end[r[t][i]]=end[t]+q[t][i];
					if(!f[r[t][i]])
					{
						d.push_back(r[t][i]);
						f[r[t][i]]=1;
					}
				}
			}
		}
		if(end[n]!=99999999)
			fo<<end[n]<<endl;
		else
			fo<<-1<<endl;
	}
	return 0;
}