#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdlib>
using namespace std;
typedef struct edge{
    int v,w,w2;
    edge(int a,int b){v=a;w=b;}
    edge(int a,int b,int c){v=a;w=b;w2=c;}
//state로 사용할 때, w는 최소 속도, w2는 최대 속도를 저장
    edge(){}
} state;
int V;
bool valid(vector<edge> adj[2001],int limit){
    for(int i=0;i<adj[0].size();i++){
        bool chk[2001]={false};
        queue<state>q;
        chk[0]=chk[adj[0][i].v]=true;
        q.push(state(adj[0][i].v,adj[0][i].w,adj[0][i].w));
        while(!q.empty()){
            state here=q.front();q.pop();
            if(here.w2-here.w>limit)continue;
            else if(here.v==V-1&&here.w2-here.w<=limit)return true;
            for(int j=0;j<adj[here.v].size();j++){
                state there=adj[here.v][j];
                if(!chk[there.v]){
                    chk[there.v]=true;
                    q.push(state(there.v,min(here.w,there.w),max(here.w2,there.w)));
                }
            }
        }
    }
    return false;
}
int main(){
    int T;
    for(scanf("%d",&T);T--;){
        int E,i,j,k;
        scanf("%d%d",&V,&E);
        vector<edge> adj[2001];
        while(E--){
            scanf("%d%d%d",&i,&j,&k);
            adj[i].push_back(edge(j,k));
            adj[j].push_back(edge(i,k));
        }
        int L=0,R=2000,ans=1000;
        while(L<=R){
            int M=(L+R)/2;
            if(valid(adj,M)){ans=min(ans,M);R=M-1;}
            else L=M+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}