#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[201][201][2],b,c,d,l,m,n,x,y,z,r[201],k[201],p[1000000],h,t;
bool bo[201];
void SPFA(void)
{
	while (h>t)
	{
		bo[p[t]]=false;
		for (n=0;n<r[p[t]];n++)
			if (a[p[t]][n][1]<k[a[p[t]][n][0]]-k[p[t]])
			{
				k[a[p[t]][n][0]]=k[p[t]]+a[p[t]][n][1];
				if (bo[a[p[t]][n][0]]==false)
				{
					bo[a[p[t]][n][0]]=true;
					p[h]=a[p[t]][n][0];
					h++;
				}
			}
		t++;
	}
}
int main(void)
{
    freopen("hardest.in","r",stdin);
    freopen("hardest.out","w",stdout);
	scanf("%d",&b);
	for (c=0;c<b;c++)
	{
		scanf("%d%d",&d,&l);
		memset(r,0,sizeof(r));
		for (m=0;m<l;m++)
		{
			scanf("%d%d%d",&x,&y,&z);
			a[x][r[x]][0]=y;
			a[x][r[x]][1]=z;
			a[y][r[y]][0]=x;
			a[y][r[y]][1]=z;
			r[x]++;
			r[y]++;
		}
		h=1;
		t=0;
		p[0]=1;
		for (m=1;m<=d;m++) k[m]=MAXN;
		k[1]=0;
		memset(bo,0,sizeof(bo));
		SPFA();
		if (k[d]==MAXN) k[d]=-1;
		printf("%d\n",k[d]);
	}
	fclose(stdin);
    fclose(stdout);
    return 0;
}