#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

const int BUF=60000000;

char Buf[BUF],*buf=Buf;

inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}

#define N 100000+10

#define INF 1000000000000000ll

typedef long long ll;

typedef pair<ll, int> Point;

priority_queue<Point,vector<Point>,greater<Point> >Heap;

int n;

ll dist[N],dist2[N];

int e,first[N],nex[N<<1],v[N<<1],w[N<<1];

void AddEdge(int U, int V,int W){

	v[++e]=V;

	w[e]=W;

	nex[e]=first[U];

	first[U]=e;

}

int m,T;

int main()

{

	int x,y,z;

//	freopen("1011.in","r",stdin);

	fread(Buf,1,BUF,stdin);

	read(T);

	for(;T;--T){

		read(n); read(m);

		e=0;

		memset(first,0,sizeof(first));

		for(int i=1;i<=m;++i){

			read(x); read(y); read(z);

			AddEdge(x-1,y-1,z);

			AddEdge(y-1,x-1,z);

		}

		fill(dist,dist+n,INF);

		fill(dist2,dist2+n,INF);

		dist[0]=0;

		Heap.push(Point(0,0));

		while(!Heap.empty()){

			Point o=Heap.top(); Heap.pop();

			int U=o.second;

			ll d=o.first;

			if(dist2[U]<d){

				continue;

			}

			for(int i=first[U];i;i=nex[i]){

				ll d2=d+(ll)w[i];

				if(dist[v[i]]>d2){

					swap(dist[v[i]],d2);

					Heap.push(Point(dist[v[i]],v[i]));

				}

				if(dist2[v[i]]>d2 && dist[v[i]]<d2){

					dist2[v[i]]=d2;

					Heap.push(Point(dist2[v[i]],v[i]));

				}

			}

		}

		printf("%lld\n",dist2[n-1]);

	}

    return 0;

}