#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>

using namespace std;

struct node {
	int v,w;
	node *next;
};

const int maxn=202;

struct distnation{
	int ans;
	bool inq;
};

node *map[maxn];
distnation dist[maxn];

inline void init()//initmap
{
	for(int i=0;i<maxn;i++)
	{
		node *p=map[i];
		
		while (p!=NULL)
		{
			node *pnext=p->next;
			free(p);
			p=pnext;
		}
		map[i]=NULL;
	}
}


inline void init_sou(int s)//init distnation
{
	for(int i=0;i<maxn;i++)
	{
		dist[i].ans=0x7fffffff;
		dist[i].inq=false;
	}
	dist[s].ans=0;
}

inline void addedge(int u,int v,int w)//add an edge
{
	node *p=(node *)malloc(sizeof(node));
	p->v=v;
	p->w=w;
	p->next=map[u];
	map[u]=p;
}

inline void relax(int u,int v,int w)
{
	if(dist[v].ans>dist[u].ans+w)
		dist[v].ans=dist[u].ans+w;
}

void spfa(int s)
{
	init_sou(s);
	queue<int> q;
	q.push(s);
	dist[s].inq=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		dist[u].inq=false;
		node *p=map[u];
		while(p)
		{
			int t=dist[p->v].ans;
			relax(u,p->v,p->w);
			if(t!=dist[p->v].ans&&!dist[p->v].inq)
			{
				q.push(p->v);
				dist[p->v].inq=true;
			}
			p=p->next;
		}
	}

}

inline void lets_go()
{
	int n,m;
	scanf("%d%d",&n,&m);
	init();
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
		addedge(b,a,c);
	}
	spfa(1);
	if(dist[n].ans!=0x7fffffff)
		printf("%d\n",dist[n].ans);
	else printf("%d\n",-1);
}

inline void assign()
{
	freopen("hardest.in","rt",stdin);
	freopen("hardest.out","wt+",stdout);
}

int main(void)
{
	int T;
	assign();
	scanf("%d",&T);
	for(int i=0;i<T;i++)
		lets_go();
	return 0;
}