#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <queue>
using namespace std;

int waynum[210],wayto[210][210],waycost[210][210],mincost[210];
bool inque[210];
queue<int> que;

int main(void)
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	int times,i,T,n,m,a,b,c;
	cin>>T;
	for (times=1;times<=T;times++)
	{
		memset(waynum,0,sizeof(waynum));
		memset(wayto,0,sizeof(wayto));
		memset(waycost,0,sizeof(waycost));
		cin>>n>>m;
		for (i=1;i<=n;i++)
			mincost[i]=1000000000;
		for (i=1;i<=m;i++)
		{
			cin>>a>>b>>c;
			wayto[a][waynum[a]]=b;
			wayto[b][waynum[b]]=a;
			waycost[a][waynum[a]]=c;
			waycost[b][waynum[b]]=c;
			waynum[a]++;
			waynum[b]++;
		}
		mincost[1]=0;
		que.push(1);
		inque[1]=true;
		while (!que.empty())
		{
			a=que.front();
			for (i=0;i<waynum[a];i++)
			{
				b=wayto[a][i];
				c=waycost[a][i];
				if (mincost[b]>mincost[a]+c)
				{
					mincost[b]=mincost[a]+c;
					if (!inque[b])
					{
						que.push(b);
						inque[b]=true;
					}
				}
			}
			que.pop();
			inque[a]=false;
		}
		cout<<mincost[n]<<endl;
	}
	return(0);
}