#include<iostream>
#include<algorithm>
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("hardest.in");
ofstream fout("hardest.out");
int g[201][201];
int n,m,v,e,w;
bool inq[201];
queue <int> q;
int d[201];
int T;
int main()
{
	fin>>T;
	while(T--)
	{
		fin>>n>>m;
		memset(g,127,sizeof(g));
		for(int i=0;i<m;i++)
		{
			fin>>v>>e>>w;
			g[v][e]=min(g[v][e],w);
			g[e][v]=min(g[e][v],w);
		}
		for(int i=1;i<=n;i++)
			d[i]=0x7fffffff;
		d[1]=0;
		memset(inq,false,sizeof(inq));
		q.push(1);
		inq[1]=true;
		while(!q.empty())
		{
			int x=q.front();q.pop();
			inq[x]=false;
			for(int i=1;i<=n;i++)
			{
				if(g[x][i]!=2139062143)
				{
					int xx=i;
					//fout<<d[xx]<<" "<<d[x]<<" "<<g[x][i]<<endl;
					if(d[x]<0x7fffffff&&d[xx]>d[x]+g[x][i])
					{
						d[xx]=d[x]+g[x][i];
						if(!inq[xx])
						{
							inq[xx]=true;
							q.push(xx);
						}
					}
				}
			}
		}
		fout<<d[n]<<endl;
	}
	return 0;
}