#include<cstdio>
#include<deque>
#include<queue>
using namespace std;
int T,n,m;
int sw[210];
int maxn=0x7fffffff;
deque<int> s[210],p[210];
int SPFA()
{
	bool inq[210]={0};
	priority_queue<pair<int,int> > Q;
	for(int i=1;i<=n;i++)
		sw[i]=maxn;
	sw[1]=0;inq[1]=1;
	Q.push(make_pair(-sw[1],1));
	while(!Q.empty())
	{
		int x=Q.top().second;Q.pop();inq[x]=0;
		for(int i=0;i<s[x].size();i++)
		{
			int to=s[x][i];
			if(sw[x]+p[x][i]<sw[to])
			{
				sw[to]=sw[x]+p[x][i];
				if(inq[to]==0)
				{
					inq[to]=1;
					Q.push(make_pair(-sw[to],to));
				}
			}
		}
	}
	if(sw[n]==maxn) return -1;
	else return sw[n];
}
int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%d%d",&n,&m);
		int fr,to,k;
		for(int j=1;j<=n;j++)
			s[j].clear(),p[j].clear();
		for(int j=1;j<=m;j++)
		{
			scanf("%d%d%d",&fr,&to,&k);
			s[fr].push_back(to);p[fr].push_back(k);
			s[to].push_back(fr);p[to].push_back(k);
		}
		printf("%d\n",SPFA());
	}
	return 0;
}